K.-U. JAHN: Eine Theorie der Gleichungssysteine init Intervall-Koeffizienten 406 _- -

n xi: i €M

ZAMM 64, 405 - 4 1 2 (1974)

K.-U. JAHN

Eine Theorie der Gleichungssysteme mit - Intervall-Koeffizienten*)

I n Torliegender Arbeit tcerden auafiihrlich die linearen G~eichungssystenie rnit Interuall-Koeffizienten diskutiert, yobei noeh auf die 3-wertige Interpretierbarkeit und die Inferpretierbarked ala Fehlerrechnung eingeganqen wird. Uber Rangbetrachtungen kommt man zu Auasagen iiber die Liisbarkeit bzzu. die Struktur der Liisung. Es werden endliche Verfahren sur Konstruktion der f isung angegebcn.

I n the present paper sy s t em of linear equations with inferuaU-mefficient~ are discused and a 3-valued interpretation and an interpretation as error-ealculu are giuen. B y rang-considerations one receives statements abozlt the solubility and the structure of the solution. Finite methods to construct the solution are given.

I3 npe;rnaraemoii p a 6 O T e nponaBonmcH 06CTORTenbHOe 0 6 c y m i l e ~ ~ e ansethmx c n c T e M ypamesrili

n p e . r a s u H n 06 uwrepnperaum HaK o p a c s e T e norpemaocreth. Ma aaanma n o p H w e B w r e K a m q n - C MHTePBaJlhHblMH IC03@@UUMeHTaMH.

TepHH 06HOCHTeJIbHO PeWaeMOCTM HJlH CTPYKTYPM peUleHH%. ICOHCTPYKUHII PeIHeHUfl .

n p H aTOM BIJHCHFIBTCR BOnpOC BOBMO?KHO# 3-&X 3HaqHOfi HHTep-

n p H B e n e H b I HOHeqHble MeTOAbI 2JUi

Nomenklatur

Vektoq :

Mat,rix+ :

x =+ Y:

X =+ Y : x s+ Y : x 5, Y : x $+ Y :

X =, Y bzw.

x t--i Y :

X a Y : x a Y :

a,:

T(9i): 2a:

Menge der natiirlichen Zahlen Menge der reellen Zahlen

(Menge der 8bgeschlossenen Intervalle reeller Zahlen) = {<zl, z,) 1 3% 3x,(zl, z, E R A z1 5 z2)) Menge der ,,Punktintervalle"

{ X I X t R} (die Potenzmenge von R) Menge aller Vektoren rnit n Koordinaten und diem aus Z( R) Menge aller Matrizen mit m Zeilen, n Spalten, deren ,,Elemente" aus Z(R) sind Afnn(Z( R)) Operation uter ~ ( i i ) mit

u xi = < inf zf, sup 2:) E ~ ( i i )

bei M * 0 (,,starke Vereinigung"), inf bzw. sup bzgl. [R, 51 Yartielle Operation uber I( k) mit

R u { -w, W }

I(R)u{<c,a),<a,--.),<c,-)la~ R )

i € Bf idf &Y

N * 0 und Abkurzung fur ,,Intervall-Vektor", ,,Vektor mit Intervall-Koordinaten" analog nie cben. X = <zl, z,), Y = <yl, y,) seien Synibole fur Elemcnto aus Z( R), 2l fur ein Element ails M,,&n(Z( R)), a fur eine reellc Zahl: zl = z, = y, = y , (,,Y stark gleich Y " )

z1 5 y , A y, 5 z, (,,X schwach gleich y'') 2, 5 y, (,,X stark kleinergleich Y") z, 5 y, A z, 5 y, (,,X kleinergleich Y") z, 5 y, (,,X schwach kleinergleich Y") (schreibt man bei den letzten 3 Begriffcn a n Stelle von 2 iiberall <, 6 0 erhiilt man die Begriffe ,,stark kleiner", ,,kleiner", ,,schwach kleiner") r, = y, (,,X verkettet Y") y1 5 x, 5 z, 5 1, (,,X feinergleich Y") X 2 Y A X * Y (,,X feiner Y") <a, a) (alle angefiihrten Operationen und Reletionen sind fur Vektoren und Mrttrizen entsprechend element- weise zu vemtehen) (,,Menge der reellen Teilmatrizen von a") = { @ $e Man( R) A %, 2 % } Familie der Zeilenvektoren+ von I in der durch die Zellennumerierung von % vorgegebenen ZU-

3 4 a E R A Vi(i E M - a E Xi)) (,,starker Durchschnitt"), inf bzw. sup bzgl. [R, $1

X = Y: z, = y, A z, = y2 (,,X gleich Y")

(,,Punktinterv811 a", ,,entartetes Intfrvall a")

ordnung entaprechende Familie der Spaltenvektoren+ von %

(,,Determinante+ von a") $a:

(fiir m = n) det IH, III: {IQ I B E T(W1 E Det %: ( -1)x(p) W) ... yp, ' (n)

P (fiir m = n) (,,Determinante von a'')

*) Aus der Dissertation des Verfassers, Leipzig 1971 47

406

rg '%: nie im Klassischen definiert, nur uber det 9l und unter Benutzung der Relation =+ Rg %: analog wie eben, nur uber Det 2.

a,, ... , ak sei eine Faniilie von Vektoren, gleicher Lange wie die des Vektors+ a, At E R: a,, ... , ap hear , unabhhngig: L,a, + I.. + Axar =* 8 nur moglich fur A, = e . 0 = i l k = 0 a,, ... , ak linear, unabhangig: fur alle i niit 1 5 i 5 k gibt es ?it E !!'(at) mit Z,, ... , ' i k sind linear unabhnngig a,, ... , a& linear+ unabhangig: d,a, + ..- + Aka* =+ 8 nur moglich fur d, = = Ak = 0 a,, ... , ak linear,, o, + abhangig: a,, ... , a& nicht linear,, o, + unabhiingig rn(al , ..., ak):

K.-U. JAHN: Gine Theorie der Gleichungssysteme rnit Intervall-Koeffizienten

niaximal mogliche Anzahl von Vektoreq einer linear, unebhangigen Teilfamilie von (a,, ..., ax) - - = Rang, von (a1, ..., at).

rda,, ... . a d : wie eben definiert nur uber lineare* Unabhiingigkeit = Rang+ von (a,, ... , ax). a LKB, der a,, ... , a&: a =+ dlal + . -I + Axat fur gewisse E R a LKB, der a,, ... , ax: fur jedea i? E T(a)

gibt es Er E T(at) mit

a LKB,, der a,, ... , ok: a =+d,a, + eine Linearkornbination dieaer G,, ... , ?ik

+Aka, fiir gewisse E R .

1. Einleitung Im AnschluD an die Arbeit [3] (wid auf dieser aufbauend) wollen wir in dieser Note eine systematiwhe Theorie der linearen Gleichungssysteme rnit Intervall-Koeffizienten entwickeln. Wir werdcn daher hier schon in [3] definierte Begriffe verwenden. Auch in dieser Arbeit w i d neben deni formalen Aufbau der Theorie, die eine Erweiterung der klassischen Theorie ist (fur gegen Null gehende Intervallangen ergibt sich gerade diese) und im Rahmen der Intervall-Rechnung strukturell erfel3t wird, wieder auf die 3-wertige Interpretierbarkeit und damit im Zusammenhang auf die Interpretierbarkeit als Fehlerrechnung eingegangen. In Definitionen wird zur Abkurzung von genau dann, wenn wieder gdw. benutzt .

2. Grundlegende Definitionen ; Moglichkeiten der Interpretation

Sei 9l eine Matrix,, '$3 ein Vektor, mit '21 E Mmn(I( R)), b E Vm(I( R)) fur ein m, n mit 118, )t E N. Dann heiDe X = ( X t ) E (PRY die Losung des Gleichungssystems, 9IX A, B gdw. fur jedes i mit 1 5 i 5 n ist Xi die Menge der i-ten Koordinaten aller Losungsvektoren aller reellen Teilsysteme von %E --,, a, wobei ein reelles Teilsystem von A+ 23 ein linesres Gleichungssystem %x = @ rnit E T(%), @ E T(B) sei.

Genm im Falle E = 0 (was also Xi = 0 fur alle i bedeuten soll) heilje %X -: + !I3 unlosbar.

Die Wahl des Symbols ,,A++'' soll auf eine Modifizierung von ,,= +" aufmerksani machen, deiin fur X E I',,(I( R ) ) gilt ja bei obigen E, 23: f die Losung von 91% A 8 8 (was wir auch einfach durch Aufschreiben von 91% A+ b ausdriicken wol- len), so 21% ==+ 8.

Es gilt nun: FaDt man die Intervalle von % und 8 als Niiherungswerte (von gewissen unbeksnnten wahren reellen Werten) plus Fehlerschranken auf, wobei also der wahre Wert garantiert Element des so entstehenden entsprechenden Intervalls sein soll, so gilt fur jeden Losungevektor x des wahren linearen Glei- chungssystems -I+ @ ist: g E 5 (wobci E koordinatenweise verstanden werden soll). 1st zusatzlich fur jedes i die i-te Koordinate X t von X beschrankt (was uber = @ eindeutig losbar bedeutet) und nimmt man als Naherungswert der i-ten Koordinate z' (fur jedes i ) des wahren Losungsvektors den Mittelpunkt i? des Intervalls UX*, so hat man in d ( U X f ) / 2 den kleinstmoglichen absoluten Fehler fur z*, d. h.

= @ (im Falle dessen Losbarkeit), wenn X =+ 0 die Losung von

= g losbar auch

und engere Schranken anzugeben - nur auf der Grundlege der obigen Informationen - ist niemand in der Lage. Diese Betrachtungen zur Fehlerschranken-Interpretation bei Gleichungmystemen, sind damit nur sinnvoll, wenn jedes reelle Teilsystem eindeutig losbar ist, de zunlichst kein reelles Teilsystem vor einem anderen in bezug darauf, das wahre System zu sein, ausgezeichnet ist und auch dann X E Vn(I(R)) fur die Losung I gilt.

1st nun (Za) E V,( R) und Z = (X') E V,( PR) mit X die Losung von 3% A+ 8, wobei 9 l X A+ ??3 fur ein eigentlich gemeintes klassisches System = % stehen soll, dessen Koeffizienten man eben nicht genau kennt, so weiD man fur jedes i folgendes, falls jedes reelle Teilsystem von %X - + '$3 losbar ist:

X z 4 2 ist nicht die i-te Koordinate eines Losungsvektors von %x = B; 2* E Xi und d ( U X 2 ) > 0 -+ es ist nicht zu entscheiden, ob LL die i-te Koordinate eines Losungsvektors von %x = 8 ist oder nicht. 1st jedes reelle Teilsystem von %XI,+ b losbar --t @x = F8 ist losbar; ist kein reelles Teilsystem von %X A+ 8 losbar -+ %z = %j ist unliisbar; gibt es sowohl losbare als auch unlosbare reelle Teilsysteme + es ist nicht zu entscheiden, ob $$z = @ lijsbar ist oder nicht ; usw.

Wir definieren nun noch fur %, L! E MnEn(I(R)), 23, 5D E V,,l(I(R)), (3 E M,,(I(R)), Sj E V,,(I(R)): X = (Xi) E E (PR)" heiDt die Losung des Gleichungssystems, % I f + 23 A+ % bzw. PIE + b A+ E X + FD bzw. 3 * ,+

A+ qX + 23 gdw. fur jedes i mit 1 5 i 5 n ist X' die Mcngc der i-ten Koordinaten aller Losungsvektoren aller reellen Teilsysteme + @ = % bzw. '$i~ + '@ = Ex + % bzw. x = '& + '$j von 91E -t- 8 -le %

gi t 22 und d ( U X L ) = 0 -+ 2 ist die i-te Koordinate eines Losungsvektors von '& = @; Zt

K.-U. JAHN : Eine Theorie der Gleichungseyetemts dt Intenrall-Koeffizienten 407

bzw. IX + B A, GZ + % bzw. Z A, IX + 12). Genau im Falle X = 0 heilk das entsprechende Gleichungs- syBtem, (System,) unlbbsr, sonst liiebar. Wir nennen zwei Gleichungssysteme, iiquivelent gdw. sie ent- weder beide unlbbar sind oder beide liisbar sind und in diesem Falle die gleiche Liisung beaitzen. I heiDt die Koeffizientenmatrix,, b der Vektor, der Absolutglieder des Systems, 91% * , W.

Die Matrix, (al, ... , an, b), deren Spalten also gerade die Vektoren, al, ..., a,,, b in dieser Reihenfolge aind bei I = (al, ..., a,,) heiBt die erweiterte Koeffizientenmstrix, von IZ A, b. IZ A+ '8 heiBt homo- genes Gleichungseystem, gdw. @ = 8 ist; andernfells heiDt es inhomogen. Ein homogenes System, heiOe nur trivial lbber gdw. 8 ist der Lijsungsvektor,.

a) Multipliziert mun in IX s, b irgendeine Zeile rnit einer reellsn Zahl iz + 0, so ist daa dadurch neu ent-

b) Vertawcht mun im System, IX A, b irgend zwei Zeilen, so ist daa dadurch neu entstehende Syatem, mit

c) Es sind die System, IX + b=+ % und

Satz 1: I, Q E Mm,,(I(R)), b, '3 e Vm(I(R)) , @ 6M,,(I(R)) , 8 E V,,(Z(R)); dann gilt:

stehende Syatem, mit %X A, b ciquivalent;

%Z =, b ciquiualent;

IX =, (% - b), ((3, - @ ) X = * Q , @?&A*@ Und Z&@* -a)%+@, I Z + b = , Q X + % u n d

Zs,@,s+Q und

(2( - Q) %A, (% - b) je ripuivalent.

S a t z 2: % = (al, ... , a,) E M,&(R)), b E Vm(I(R)); dann ist dm System, IX A, 8 genau dann liisbar, wenn b eine LKB, der al, ... , a,, ist.

Mit Hilfe dieses Satzes kann man nun sofort einen Algorithmus zum Auffinden der Losung (im Falle der Existenz) eines beliebigen Gleichungesystems engeben bzw. man atellt feat, dsB das System unliisbar ht; wir werden uns damit unter 4. beschiiftigen.

Sa tz 3: (Hauptsatz iiber homogene Gleichungssysteme,) Ein System, %X 2 , 0 mit I E Mm,,(I(R)) ist stets hbar und jiir die L&unq X gilt iX E V,(Z( R)), wobei

eine Koordinate, w o n % nur die Gestalt 0, oder <+, 4) h&n kann. E8 iSt Z = 8 genau dann, wenn r,(Y'a) = n ist. Damit ist rg % = n hinreichend dajur, da# 8 = 8 id. Es hat X mindatens eine Koordinate+ der GestaU (t, -+) genau dann, wenn r,(Y'a) < n ist; eine hinreichende Bedingung k j u r ist damit m < n. Bei m = n iSt rg I = n ndwendig und hinreichend dajur, &# IZ A, 8 nur trivial h b a r ist.

3. Charakteristische SUze tiir (fleiehungseysteme, mit quadratischer Koetfizientenmatrix, Zusiitzlich zu den unten angegebenen Sachverhalten ordnen sich diem Systeme, natiirlich auch der allge- meinen Theorie unter.

Sa tz 4: % = (al, ... , a,,) E M,,(I(R)), b E V,(I(R)) jiir ein n mit n E N; dann gilt: Jedes reelle Teilsystem w o n IZ A,+ 23 ist eindeutig f ibar .-. rg B = n ;

es esiatiert ein unliisbares reelles Teihystem + r+(J") < ro((Y'a, 8)) (+ r+(Y'a) < n) (($a, 8) sei die Familie der Spaltenveben, der erweiterfen Koejjizientenmatrix,) ; r,(Y'a) < ro((Y'a, b)) -+ es gibt ein un&bara reellee Teihystem; r,(Y'a) = r,,((Y'a, b)) < n oder r,(Y'a) = ro((Y'%, 8)) < n -P es gibt ein mehrdeutig liiabares reeUes Teibgstem von 2lZ A+ b.

Satz 5: I E M,(Z(R)), 23 E V,,(Z(R)), I = (A*'), b = (B*). EnthCilt dw System, IX A, b sowohl ein h b a r a ale a w h ein u n h b a r a reelles Teibystem, so ist mindatens eine Iloordin.de der Lb8ung Z unbachrdnkt.

S a t z 6: a) Daa System, IX =+ '23 mit reg&rer Kmjfiziedenmatrix, B E M,,(I( R ) ) besitzt die Lissung

Z = U U A-1 - @), E Vn(I(R)) . K€T(Ql) ih.78)

b ) Ist X E Vn(I( R ) ) jiir die Usunq Z des System, IX + b mit I E M,,((Z( R)), so I reg&r.

liisbar und Z E V,,(I(R)) fiir die sung X - B reguliir; det % =+ 0, und det $?I +* 0, -+ IZ A+ 93 16sbsr und X unbeschriinkt fur die Liisung X ; det % =, 0, : entweder

Aus den Siitzen 4,6, 6 ergibt sich also fiir aleichungssysteme+ A, '$3 mit I E M,(I( R ) ) : 2lZ i+ b

++ b ist u d b b a r oder L, ist liisbax mit I unbeschriinkt fur die Lasung 2. Wir gehen k u n auf den Fell n = 2, % reguliir ein: Es gilt hier sofort f i r die Liisung X = (Xr):

27*

408 K.-U. Jm: Eine Theorie der Gleichungoaysteme mit Intervdl-Koeffirienten

Wegen det 8 ++ 0, gibt ea nun in jeder Zeile und jeder Spalte von N mindestene ein Air mit A'' ++ O,, a h Ala, Aal+* 0, oder 811, A*' ++ 0,. Auf Grund von Monotoniebetrachtungen erhidt man folgende Lbungsformeh ( fa ein Interval1 A war (A), der linke, (A), der rechte Randpunkt von A):

A'S, A*1 *+ 0, :

Ein Qleichungssystem, %X A+ b mit % E M,(I( R ) ) , det N ++ 0, liiSt dch immer durch (1) oder (2) lasen. Im Rinzip Bind diese beiden Formeln schon in [l] hergeleitet, jedoch treten dort solche Begriffe auf wie , ,Hue abhiingiger Intervelle", die wir nicht verwenden.

Fiir n 2 3 bekommt man keine so einfachen Formeln zur Besthmung der Usung.

Satz 7: 1st E E V,,(I(R)) die m n g des 8ystetnt?, 82 +,. b mit regdirer Matriz, % E M*(I(R)), 80

gibt ea fur jeda i, j mit 1 5 i 5 n, 1 5 j 5 2 ein r e e k Teilsystem Ni,E = &, von 832 A* b mit sogar noch as, reelle Randmatrix von %, @,, reekr Randuekcor von by 80 duJ die i-te Koordinate &es ~ n g . s v e k t o r 8 fg&ich dem Randpunkt (X'), der i-ten KoordiW.+ dea l5ikwqweektOrs, X von

Folgerung: Man kann die Lasung 32 des Systems, N3E A+. b mit regullirer Koeffizientenmatrix, % sofort angeben, wenn m&n die Menge M aller Liiaungen aller solchen reellen Teilsysteme $@ = @ von %?I% &+ b kennt, fiir die gilt: % reelle Randmatrix von 9l, % reeller Randvektor von b. Es ist dann niim- lich X = LIZ,.

- - A+ b ist.

%lbf

Betreohten wir zwei Beispiele: Beispiel 1 :

<I, 2) X' + <9, 9) X' A+ <IS, 17) <2,3) X' + <1,1) X' =.+ <3,8);

det QI = <-26, -16) <, 0,. Anwenden von (1) ergibt X1 = (6/13,67/16>, X* = <7/8,24/13). Far die Berechnung der b u n g nach Satz 7 genugen hier echon zwei Randaystame.

Beispiel 2: <1,1) X' + <4,4) X' <4,6) X' + <-4, -3) Xa+. <2,4);

<5,8)

det Q I = <-!24, -19) *+OF. Anwenden von (1) ergibt XI = <1,12/6), X' = <4/5,38/23). Fiir die Berechnung der Lijeung nach Sstz 7 brsucht man her jedoch vier Randsysteme.

Es gilt nun sogar noch der folgende

Setz 8: PIX ++ 8 mit reg&rer Matrix* %, { gl, ..., a h } die Menge der reeUen Randnaatrizen won %?I, k; dam giat fiir die Lbeung X urn NX A+ b: & := $ 8 ~ ~ fur alle i mit 1 4 i

z = I5 (Q'S) i-1

Wir haben nun weiter unbrsucht, ob bereits E = (&s) ist, wobei { ..., &) die Menge derreollen hndmatrizen @ = (det %)a ( a:' = &). Fiir unser Beispiel 1 ist 8 = /J&8),

i-1 2 von QI ist, fiir die gilt: % E { g1, ..., at) gdw. fiir Beispiel 2 j d o d nur u (&s) a 8.

= (det oder a

(-1

Satz 9: 8 E M,,(I(R)), det 8 ++ 0, ; dann 8ind die #palten von 8-l gerade die Lasungen deer n Q&khu?8gs- 8yeterne, $E' A, b' (1 5 i 5 n) wobei gil t , die i-te Koordinate, von 114' eei 1, , alle iibrigen seien gleich 0, , wnd zzcrar wt dunn %-I= ( E l , ... , P).

Satz 10: % E M,,(I(R)), det a$+ 0,, M := (Yenge aUer Inversen aZ&r reekn Randdr i zen w o n a), M, := 1 a-1 E M I ; dann iat %-I= u M, .

K.-U. JAEN: Eine Theorie der GleichungMlyetema mit Intervall-Koeffizienten 409

Im allgemeinen gilt nur (%-1)-1 D o[, sofern %I nnd %-I reguliir eind: Sei @ o T 8); dann ist 2 9l-l und ($f-l)$ oeffisientenmatrix+ 9[ unserea obigen d -

= at s(H-lj-1, also Ql s (Ql-I)-l. Ein'Beiiiel fiir BeispieKl. Hier iet

91-1 =

*,, % liefert echon die

<-l/l6, -1/26) (9/26,9/16) (3126s 1/8) <-I/& - 1 / W

(etwa iiber Sata 9 oder Satz 10 ausrechnen). Fiir dss Element P1 der Matrix+ B := ergibt eioh nun D11= 1/(<-1/16, -1/26) + <27/676, 9/128)/<1/26,1/8)) = (832/1621y 2704/696) D <I, 2) = A''.

Satz 11: Sei E die Libung von BE A+ b, B reguliir; dunn gilt E 9 %-%. Ftir unser obiges Beiepiel 1 iat

<-6/208, 816/208)) I> ((6/13, 67/10)) = E . (718, 24/13)

%-I@ =

4. Der sllgemeine Fall Satz 12: B = (aly ... , a,) E Mm*(I(R)), 8) E Vm(I(R)); genuu &nn b t jeh reeUe Teilsystem von NEI, b eindeutig &bar, wenn n = r+(al, ..., a,,) = ro(aly ..., a,, b) bt.

Die iibrigen Auseagen von Satz 4 gelten auch fiir beliebige Systeme+ BE &+ b mit % E M,&( R)). Satz 13: %=(a1, ... , am)T E Mm,(I(R)), b = (P) E V,,,(I(R)); dunn gilt: Jede.8 reek Teiby8tem von

Atat der Zeilenvektoren, von % mit C A i d =* 8 gilt C A i B = 0, (I) #I #I

A+ b ht &bar - fiir jede LKB, (-1 (-1 i=l

mit obigen 1,. (.Fredio~m8che Alternative f4ir Ulekhung88ysteme+). Damit ist jedes reelle Teilaystem von QlE b lbbar, falle HT9 A+ 8 nur trivial liisbar iat. Ist jedee

reelle Teilaystem von 9I3E - * + b lihbar und r.&, ... , a,) = n bei B = (al, ... , a,,), 80 iat jedea reelle Teilaystem eindeutig lbbar.

Spiiter werden wir noch sehen, da8 am E E V,(I( R)) fiir die Lhmg E dea Systems, %E A+ b nicht

Aus Satz 13 folgt nun etwa noch fiir Spteme+ BE A+ 93, % = (a1, ... , am)T E iK,,,,(I( R)): 1st C &at =+ 8

miiglich mit l i e + 0 fiir ein i, mit 1 5 i, 5 m und A S > 0, 80 enthiilt 8% A+ 113 ein unliieberes reelles Teilsystem. So enthalten auch Spteme, mit m > n and AB' > 0 fiir alle i mit 1 i 4 m sofort unliisbare reelle Teilsysteme. Ober Satz 3 folgt, da8 jedee reelle Teilaystem von BE =+ b hiichstens dam eindeutig lbbar iet, wenn 8% A+ 8 die Liisung Ze = 8 beaitzt.

a) 1st jedm reeh Teikystem eindeutig &bar, 80 giu Ze E V,,(I(R)). b) 1st jedee reeUe Teilsystem &bur, 80 h t

Damit gilt also auch: 1st E 6 Vn(I(R)) fiir die Liisung E dea Systems+ BE A+ b bei B E Mmn(I(R))y 80 enthat BE t-+ 8 ein unlkbares reellee Teilsystem. Die umgekehrte Richtung hiervon gilt nicht, me wir dann noch sehen.

Satz 16: % = (At') E Mm,,(I(R)), 8 +,, 93 E V,(I( R)), m> n. S i d dunn a& E&me& A*' nic7ctentartete Intervalle, so bed& a1E A+ b ndwendig ein nicM eidut ig &bare8 reelles Teileyetern.

Ftir B E M m S ( I ( R ) ) , 8 +, b E Vm(I(R)), m > n gilt also auch: 1) Sind alle nichtentartet und ist r+((u"a) = n, 80 beaitzt 8% A, B ein nicht lbbares reelles Teilsyatem. 2) Gibt es eine n-reihige quadratiache Untermatrix, %,, von 8 mit det 9.L +, 0, und gibt ea weiterhin eine

Bile a d o von %, die nicht in diesea 9&, eingeht und deren siimtliche Elemente nichtentartete Intervalle eind, eo entbiilt QlE A+ 8 ein unlbbme reellee Teilaystem, falls noch fiir das zu diesen n + 1 Gleichungen gehiirende Stuck 8,,+1 von 8) gilt: bn+1 +, 8.

3) Gibt es eine n-reihige quadratiache Untermatrix, %,, von % mit det 9.L +, 0, und gilt b, =, 8 d t b,, E V,,(I( R)) und B,, entsteht am b durch Streichen deraelben Zeilen, die bei 9l geatrichen wurden urn %, zu bekommen, 80 enthat %E A+ 84 ein unlhbares reellee Teilaystem.

@ E Vm(I(R)). GiL dann 2ie =+ 8* fiir die i,-k Zei& 2,0 von (a, b), so s i d L+ % dquivalent, d e i (a, %) au8 (By '$3) durch 8treichen &r i,-ten

unbedingt folgt, deJ3 dann jedee reelle Teilayatem eindeutig lihber ht. #I

i-1

Sat2 14: BE&, 8 &%bare8 G&khung88y&m+ md % E Mm,(I(R)), % die h n q .

E V,,(I( R)).

Satz 16: 9I E M m B ( I ( R ) die beiden Sy8km+ BE A+ A und Zeile von (B, b) iervorgehe.

a) Ui& dunn fiir ein 9 E V,(I( R)) die Bezkhung Ng 9 b, 80 iet BE &+ b &bar und e8 gilt 9 9 U E fiir die

b) I8t jede8 reek Teil8y8te?n von

Satz 17: 9I E M,,,,,(I(R)), b E V,,,(I(R));

Ldgung E m WE *+ 8. A+ b &bar, 80 giu b fiir die &bu?zg E m L+ b.

410 K.-U. JAHN: Eine Theorie der Gleichungssysteme mit Intervall-Koeffizienten

\Vir entwickeln nun auf der Grundlage unserer bisherigen Theorie einen Algorithmus, der es gestattet,, bei jedem Gleichungssystem, entseheiden zu konnen, ob es losbar ist oder nicht und im Falle der Losbarkeit die L o ~ u n g explizit anzugeben (die folgenden Systeme von Ungleichungen finden wir fur einen Spezialfall schon in [2]).

Fur 9( E Mmn(I(R)), 91 == (al, ... , an), B E V,(I(R)) gilt nun nach Satz 2: !JIM;.-+ @ losbar - '$3 ist eine LKB, der Vektoren, von 9". (8 ist eine LKB, der Vektoren, von

YQi) ist nun aber wiederum aquivalent rnit 32(% E V,( R) A 9i.g =+ '$3). 1st nun 'EX . + % losbar, so gilt bei X = (F) die Losung fiir jedes feste i, rnit 1 5 i, 5 n : x E Xi. - es gibt reelle Zahlen A,, ... ,A,, mit At = z

und xAlnl -+ B, wie man sofort aus der Definition der Losung eines Gleichungssystems, ersieht. ,41so

gilt der .e 8 bei 91 E Mmn(l(R)) Z6sbar. Dann gilt fiir jedes feste i, mit 1 (= i, 5 n : KG ist

die i ,-te Koordinate, der Ldsung X von '$iX 1 ,,. b 6, X i . == (Menge allcr i,-ten Koordinaten aller .g E V,(R)

Narh diesem Satz konnen wir die Losung X von U X . ,+ '$3 sofort mgeben, wenn wir alle X E V,(R) mit '5Jz kennen. Wie diese ermitt.elt werden, zeigt der folgende Satz. Fiir zwei Intervalle A = (.4,, -+I2), B = (Bl , B,) gilt. ja -4 =+ B - - A , 5 B, A B, 5 A,:

S a t z 19: ?I = E AZ,nIl(I(R)) , 23 = (B ' ) E i 7> ,z ( I (R ) ) , z = (2) E V,(R). Dnnn. iut 91% =+ 23 - j. 1 j - 1 ( (j="l 1, (j:: ii) -+t/.j 1 5 ~ 5 m . . ~ ~ A i i . i . ' ~ , B ' A B ' ~ , , ~ ' 4 ~ l ~ j ) - V i 1 sis?n+ ZAtf .? S(B'),A(B'),S x A t i % ' .

= (Azi) E Mmn(I(R)), Air = (Aij, A?), '23 = (B') E Vn,(Z(R)), Bi = (Bf, B6) vorgegeben und ist Jl := {z I 1 = (5') E V n ( R ) A ?lx --+ B}, so ist wegen ).(A,, A 2 ) = <l.Al, ).A2) fur 1 2 0 und

A(Al, A,) = (),A2, AA,) fiir A 5 0 dann 111 = u Aft mit : die IlIt 2 Vn( R) sind die Losungsmengen der fol- genden 2" Syst,eme von TJngleichungen:

I 1

j = l

S a t z 18: Sei % X

nlil BIX -.* 8). -

Sind nun i

2"

k- I

Genau dann, wcnn M =+ 0 ist, ist 9IX A, 23 losbar und die Losung W kann dsnn &us 1cI nach Satz 18 kon- struiert \r erdcn.

1st nun eine Koordinate von X eine nicht-zusamnienhangende Punktmenge, so wissen wir sofort nach Satz 14, daB % X &+ B ein unlosbares reclles Teilsystein enthiilt.

1st bereits 91 E Mnt,b(I( R,)) und 8 E VnI(I( R*)) , d. h. liegt pra.ktisch ein klassisches Gleichungssystem vor, so reduzieren sich die obigen Systeme von Ungleichungen auf eben dieses Gleichnngssystem, und alle unsere Aussagen gelten auch fiir diesen Fall.

5. Honstriiktion von Obermengen der Losung

Man bekornmt eine Obermenge der Losung, wenn man formal den GAussschen Algorithmus mit, d m Opcra- tionen der Intrrvall-Arithmetik durchfuhrt ocler, bei BI E M , ( I ( R ) ) rnit sogar Det 91 $+ O , , formal die CRA- xrEaschtl Regel anwendet. Ebenso etwa durch Anwenden von Satz 11 oder durch Verwenden voii solchen RIetlioden wie etms, das in [2] und [4] beschriebene Auswerten von rationalen Intervallfunktionen mit Hilfc der ,,Zentrischen Form" der rationalen Funktion usw.

K.-U. JAHN : Eine Theorie der Oleirhungssysteme mit Intervall-Koeffizienten 41 1

Das folgende Verfahren ist eine Modifikation des GAussschen Algorithmus auf Gleichungssysteme,. Sei ein Gleichungssystem, %X ++ 23 mit 2I.c Mmn(I(R)), '23 E l'm(I(R)) gegeben, % = (,4tf), B = (Bt) . Wir

bringen nun 9l folgendermd3en auf die Gestalt i1 = (All) mit ++ 0, fur 1 5 i 5 r (5 min { m , n } ) , A'' =: 0, fur i > j 5 r , At? =+ 0, fur i , j 2 r + 1, wobei wir der Einfachheit halber annehmen, daB die Zeilen und Spalten von % bereits so je untereinander vertauscht sind (was keine Einschrankung der Allge- meinheit bedeutet), dal3 bei keinem der im AnschluB beschriebenen Rechenschritte eine Vertauschung vor- genommen zu werden braucht. Das sol1 bedeuten, daB, wenn 91 die nach dem 1-ten Schritt (1 2 0, % := PI) aus '21 entstandene Matrix, ist, entweder A'-+'> z-+-l ++ 0, ist oder Aif =+ 0, fur i 2 I + 1, 1 s j I - n

ist. 1st Ail = Ail =,+ 0, fur alle i , j, so hat % bereits das gewunschte Aussehen (r = 0) und wir eind fertig. Andernfalls ist A" ++ 0, ( r 2 1).

r r

1 0

0 I 1

0

0

0 0 0

1 . Schritt: Wir addieren die All-fache v-te Zeile zu der (-A*')-fachen ersten Zeile von 91 und ersetzen

die ursprungliche v-te Zeile von % durch diese eben neu gewonnene. Das machen wir so fur alle Y mit 2 v 5 m und A*' + O , , lassen die erste Zeile von % unveriindert und ersetzen noch alle ersten Elemente der 2-ten bis m-ten Zeile durch 0,. Die so aus 2 erhaltene Matrix, bezeichnen wir mit 3. 1st nun A22 =+ 0, , so ist

r = 1 und wir sind am Ziel. 8ei A'' ++ 0, fur 1 5 s < k. 1st Akk =+ 0,, so ist r = k - 1. Akk ++ 0, :

k-ter Schritt: Wir addieren die Akk-fache v-te Zeile von 3 zu der (- Avk)-fachen k-ten Zeile von 91 und

rrset,zen die v-te Zeile von PI durch diese eben neu gewonnene. Das machen wir so fur jedes v mit k +. 1 5 v 5 na

und Avk =!= 0, , lassen die ersten k Zeilen unveriindert und ersetzen noch alle k-ten Elemente der (k + l)-t.en

bis m-ten Zeile durch 0,. Die SO aus % erhaltene Matrix, nennen wir 91. Wir fuhren insgesamt r Schritte durch, bis die dann ent'ktandene Matrix, 91 zum ersten Ma1 das oben beschriebene Aussehen hat. Es gilt nun:

0

0 0

0 1 1

8-1 k - 1 k - 1

k - 1 k - 1 k - 1 k - 1

k -- 1

k - 1

k - 1 k

r

r r = rg PI = r,, ( YiI) = r , (J i ) 5 r,( 2 ~ ) .

r Weiterhin gilt rg % 5 rg % (wir zeigen das spater) und damit r,(Yil) 5 r,(#?I), r+(Jx) .

Kun fuhren wir den obigen Algorithmus an der Matrix, Q := (91, 23) E Mm,nTl(I(R)) durch, wobei die letzte Spalte von 6 ist und nicht mit inderen Spalten vertauscht wird und hochst,ens n Schritte durch-

gefuhrt werden. Hier bekommen wir dann die Matrix+ & := ('&, 6) a1s Ergebnis. Es gilt dann der r T

S a t z 20: Ist das System, %X A+ 2.3 lesbar, so auch

Mit Hilfe dieses Satzes kann man den folgenden Satz beweisen:

S a t z 21: PIX A+ B liisbares Gleichu.ngseystem+ mit der L8sun.g X, 91 E M,,,,,(I( R)). Dann kann im Falle

Fur jeden der beiden Falle geben wir ein Bcispiel an:

A+ 23 und es gilt X 9 fur die Ld.w.ngen.

der Existenz eines unl6sbaren reellen Teilsystems sowohl X beschrrinkt als auch X unbeschrrinkt sein.

(+' -1'2)) ist unbeschrlnkt. Es ist (' ') = (i-) losbar, ( ') 2 = ( i) unlosbar und die Losung X = (<7/4J *> 3 3 3 3

(3 unbeschrankt folgt bei diesem Beispiel auch schon aus Satz 5 . ) Bei diesem Beispiel ist ein beliebiges reelles Teilsystem entweder eindcutig lbsbar oder nicht liisbar. Es braucht also kein mehrdeutig losbares reelles Teilsystem zu geben dafiir, daB die Losung 3E unbeschrankt ist.

2) (293) (191) (192)

(091) (2,3) (3,3) 91 := ( (0 ,2) (0 , l ) ) , %:== ((2,2))

0

Mit Hilfe unseres letzten Verfahrens bekommen wir aus der Matrix, Q := (2, B), indem wir das (-2,O)-fache der ersten Zeile zur (2, 3)-fachen zweiten und da.s (-1, 0)-fache der ersten zur (2, 3)-fachen

412

dritten addieren usw. die Matrix,

K.-U. JAHN: Eine Theorie der Gleichungssysteme mit Intervall-Koeffizienten

1 i 1 1

(293) 1, (1,2)

0, (399) (4 ,9)

1 1 1 6 = (3, B) = 0, ( -2 ,3) (0, 6) .

Fur die Losung @ des Systems, '219 . + %3 ergibt sich nun sofort iiber Satz 16: Y* = (4, 9)/(3, 9) = (419, 3) , Y' = ( (1 , 2) + (-3, -4/9))/(2, 3) = (-1, 719) I

Damit ist nach Satz 20 2 beschriinkt und das Sysem,313% I+ B hat also kein mehrdeutig losbares reelles Teilsystem, wie auch schon %us rg % = 2 folgt. Fur die Losung X ergibt sich X1 = (114, 3/5), X2 = (415,312) ; von den 4 Systemen von Ungleichungen ist niimlich nur des System

51 2 0, 5 2 2 0, 2x1 $- 5 2 5 2, 2x2 5 3 , { 1 5 3x1 + 5 2 , 2 5 2x1 + 5 2 , 3 5 51 + 3x2 __

losbar und der zuliissige Bereich ist gerade die Strecke POPl mit Po = [1/4, 3/21, PI = [3/5,4/5]. Wir zeigen nun noch rg '& 5 rg % fur obiges i, a: Fur 91 E Mm,,(I(R)) ( 9 7 ~ N,,,,,(R)), r 5 m, n entstehe !&(ar) aus %(a) dadurch, daB man die letzten m - T Zeilen und letzten n - r Spalten von %(a) streicht.

Sei nun eine beliebige reelle Teilmatrix von 91, wobei wir von 8 wieder annehmen, daB die Zeilen und Spalten von bereits so angeordnet sind, wie wir es vor Durchfiihrung des Algorithmus Iu --f 91 vorausgesetzt hatten. U'ir fiihren nun an $1 dieselben Rechenschritte durch, die a in 6 iibergefiihrt haben, d. h., wir iden-

tifizieren einfach

r

- mit a, fur diese Rechnung. Dabei m6ge dann '& aus a entstehen. Nun gilt sofort:

I I I r r rg ar = rg hr und weiter ist stcts rg Gr = r , da (Qi,), 3 6, und det (ir, = 17 Ati +,, 0, ist. Also ist

r r i - - 1 auch det 91r ++ 0, und damit wegen rg '$1 = r ist rg 91 5 rg 8.

Literatur 1 APOSTOLATOS, N. und KULISCH, U., Grundzuge einer Jntervallrechnnng fiir Matrizen und einige Annendungen. Elek-

2 HANSEN, E., Topics in Interval Analysis. Oxford, Clerendon Press 1969. 3 JAHN, K.-U., Eine auf den Intervall-Zahlen fnBende 3-wertige lineare Algebra. Erscheint in den Mathematischen Nach-

4 MOORE, R. E., Interval Analysis. Prentice Hall, Inc. Englewood Cliffs, New Jerscy 1966.

Eingereicht am 19. 7. 1973

Anschrift: Dr. KARL-UDO Jariw, Sektion Matlicmatik der Karl-Mars-Universitit, 701 Leipzig, Karl-Marx-Platz, DDR

tronische Rechenanlagen 10 (1968).

richten.