J. W. SCHMIDT : Uberlinear konvergente Nehrschrittverfahren vom Regula falsi- und K e w t on -Typ 103

J . W. SCHMIDT

Uberlinear konvergente Mehrschrittverfahren vom Regiila falsi- und Newton-Typ

dusgehend oon der Regula falsi und deni N e tat o n - Verfahren zur Losung von nichtlinearen G'leiehuiLgssystenieiL u!erden Xehrschrittverfahren entwickelt, welche sich gegenuber den Standardverfahren hinsichtlich der Effektivitat in zuz i Punkten auszeichnen: Sie haben einen hoheren Wirkungsgrad schon dann, wenn wian f u r den Aufwand allein die Anzahl der Punktionswertberechnungen berucksichtigt. Zusatzlich bringt die jetzt mogliche Anwendung der Form'el von S h e r m a n und M o r r i s o n bei der in jedem Iterationsschritt erforderlichen AuflGsuny van linearen Gleichungssystemen Einsparungen mit sieh. Breiten Raum nimnit die Herleitung eines allgemeinen Xonvergenzsatzen pin; er enthalt als Sonderfalle den bekannten ,Sat2 ?:on K a n t o r o i ; i c k iiber das N e w t o n , - Verfahren und ein,en ent- spreehenden Satz iiber die Regula falsi.

Starting from the regula falsi and N e w t on's method o j solving sy s t em of nonlinear equations multi-step procedures are dezeloped which in two respects have a higher effectivity than the standard methods. First, the effectivity is higher eveti if the number of function vulue computations only i s considered. Second, due to the applicability of the S h e r m a n - M o r r i s o n formula, the solution of the linear equations required in each step of the procedure can be effected with less effort. N u c h space i s given to deduce a general convergence theorem containing as special case8 the well-knoum K a n t or0 v i c h theorem on N e w t o n ' s method and a corresponding theorem concerning the regula fulsi.

Khnb3ymI, npasmoM JIOSKHOTO nonoxeHm a MeToAoM H W T O H a Ami perueHm iremmeiiribix cMeTeM JlpaBHeHllfi BLIBOAFITCFI MeTOHbI MHOrMX CeseHHfi, OTJlLIYalOIIIHeCFI OTHOCPITeJILHO 3#@eKTMBHOCTH OT 06bIYHbIX CHOC06OB B HByX TOYKaX: MX 3@@eKTHBHOCTb OKa3bIBaeTCR BbICUIMM TaKlfEe II B TOM CJIJ'Yae, eCJIII I3 06.6eMe pa6OT YYeCTb TOJlbKO KOJIHYeCTBO PaCYeTOB 3Ha4eHllfi @YHIEUIIII. ~OIIOjIHkITeJILHalI 3KO- IlOMMFl B 0 3 H H K a e T B C J I e ~ C T B H e B 0 3 M O l f i H O C T H I l p H M e H e H H ~ @OpMYJI mepMaHa M MOppIICOHa &lIFi~eo6- X O A M M O ~ O B KawAoM mare mwepauar? pernemm nmrefiHoii cmxemI ypanaeamii. O6111rip~o m:maraeTCn oRuaH TeopeMa CXO~HMOCTM. OHa C O A ~ P H W T n IEaqecTBe oco6b1x cny=raeB H ~ B ~ C T H Y I ~ TeopeMy IC aHTo -

I . Einleitung

11 0 B H 4 a , IPaCaloIIIyIoCH MeTOAa H I ~ T 0 H a , II COOTBeTCTBJTIoIQM8 3aKOII 0 IIpaBHJIe JIOWHOTO IlOJIOXEeHMH.

Die bekannt>e Regula falsi (Sekantenrnethode) zur Losung von nichtlinearen Gleichungen P ( X ) = 0 ist mehr- fach verallgemeinert worden ; eine umfassende obersicht hieriiber gibt das Buch von ORTEGA und RHEINBOLDT [ 5 ] . Von den obertragungen in den d-dimensionalen Vektorraum R1' seien hier zwei Moglichkeiten hervorgeho- ben. Die eine Variante, welche letztlich auf GAUSS zuriickgeht, wurde zuerst von HEINRICH (Vorlesung TH Dresden, 1955) allgemein formuliert und ist dann von BITTNER [l] analysiert worden: Uni die Konvergenz zu sichern, wird eine einschneidende Lagebedingung an die Iterierten gestellt, die auch spater nicht abgeschwacht, werden konnte. Die Konvergenzgeschwindigkeit x(d) strebt' echt monoton fallend gegen 1 fur d + 00. Gunstig ist, daD pro Iterationsschritt, nur ein Funktionswert, von E' neu berechnet, werden muS. Eine zweite Gruppc von Verallgemeinerungen (KORGANOFF [4], SCHMI DT 161) kornmt fur die Konvergenz ohne die besagte Lap- bedingung aus. Die Konvergenzgeschwindigkeit, hat unabhangig von d den Wert, ( 1 - + - /5)/2. Tlafiir ist der Aufwand mit d bzw. d + 1 P-Werten pro Iterationsschritt u. U. erheblich hoher.

Es liegt nun nahe, nach Verfahren zu suchen, die hinsichtlich des Aufwandes zwischen den genannten Fallen liegen und moglichst die erwahnte Lagebedingung umgehen. In der Tat kann man hierfiir der Arbeit von DANTLIN und PSEidkYf [3] iiber Minimierungsverfahren Anregungen entnehmen, deren Umsetzung fur nichtlineare Gleichungssysteme von SCHWETLICX [9J vorgenommen worden ist. Er gelangt zu Verfahren ?nit, 2 3'-Wertberechnungen pro Schritt und errechnet fiir sie im Rahmen eines lokalen Konvergenzsatzes ebenfalls die Konvergenzgeschwindigkeit x ( d ) , ohne eine Lagebedingung stellen zu miissen.

I n der vorliegenden Mitteilung werden Verfahren, namlich die spater MRf und M N genannten Verfahren. entsprechend der formulierten allgemeineren Zielstellung a,ngegeben, wobei zusatzlich Verfahren voni NEWTON - Typ einbezogen werden. Man hat jetzt, da Klassen von Verfahren zur Verfiigung stehen, die Moglichkeit. am diesen das jeweils gunstigste etwa mit Hilfe des Wirkungsgrades auszuwahlen. Weiter wird ein .Ronver- genzsatz fur diese Verfahren hergeleitet, der zu jener Gruppe von Satzen gehort, bei welcher sich neben det. Konvergenzaussage auch die Existenz einer Losung und eine Fehlerabschatzung fiir die Iterierten ergeben. Als Sonderfalle sind der Satz von KANTOROVICH iiber das NEWTON-Verfahren und ein entsprechender Satz (s. E ~ J K - MEISTER 121, SCHMIDT [7]) iiber Regula falsi-Verfahren enthalten. Als wesentliches Beweishilfsmit,td wird das MMajorantenprinzip verwendet (6. ORTEGA und RHEINBOLDT [ 5 ] ) .

Die Verfahren MRf und M N sind ebenso wie ihre erwahnten Vorgiinger i. a . nur lokal, d. h. fur hinreichend gute Startvektoren konvergent. Auf die Frage der Beschaffung geeigneter Startvektoren wird nicht eingegangen.

2. Beschreibung der Verfahren im Ra Es bezeichnen z = (x l , . . . , xd) E Ed einen Vektor iznti F = ( F l , . . . , Fd)lC c Wd + Wd einen Operator. Bamit kann das nichtlineare Gleichungssystem

(1) F l ( ~ 1 , . . . , xa) = 0 , . . . , F p ( ~ 1 , . . . , ~ , j ) = 0

I04 J. W. SCEIDIIDT: Uberlinear konvergente Melirschrittverfahren voni Regula t ' i ~ l ~ i - u i i d K awton-Typ

a 1s P(.r) = &.El, . , . , .Cd) = 0

geschrieben werden. Es sei D ein aclisenparalleler Quader aus dem lnnern von C, L, c lilt G. Uic partiellen Differenzenquotienten von F , auch die mit wiederholtem Argument, seieri wjr ublicli definiert : z. R. ist der erste partielle Diffrrenzeiic.jnotient von F nach dem k-ten Argument

Weiter wwde als Abkurzunp

hF(Ullk - 1 , wk zg . 1'1 Lid) hF(u1. . 3 uh 1. wk zk, 1'1 8 I , . . . v d )

vereinbart. Dann kann man fur u. v E D und 1 5 k 5 cl den Vektor 6F(u , u ; k ) durch

hF(U. 21: A") 3 rSF(Ul,/, I . Ut V k , Uk I J ~ ) ( 3 )

hl"(u, 2 ) : k ) hk'(vllA- I ) u k wk, U k + l l d ) (4)

otier auch durcb

definieren; man liest ihn zweekmaBig als Spaltenvektor. Fur v = 1c E U entsteht in beiden Fallen der Vcktor der Ableitungen nach der k-ten Variablen.

( 5 )

, d E D vorgegebene Vektoren. Dann

h F ( u . 7 c : k ) = &Flu) .

Es seien n u n t eine naturliche Zahl mit 1 kann man folgendc Matrix BF bilden:

t 5 d und w'. . u'. I ) ' . . .

v1 "'I *

dF(u8,. . . ,ul; 2 1 1 , . . . , u') = bF(ut, v t ; 1 ) . . . hF(ut , v t ; cl - t + 1) hF(ul-1,v' ' ; d - t 4- 2) . . .BP(ul,

(6) Die ersten d ~ t t 1 Spalten werden allein mit den Vektoien uL, uL sufgebaut, wlhrend die nachfolgcuden Vektoren ur, v' (t = t - 1, t - 2 , . . . , 1) genau einmal zur Spaltenbildung herangezogen werden. Fur t = 1 entsteht eine niehrfach verwendete Matrix (mit (3) s. [4], [6] und mit (4) s. [6]).

Als Moglichkeiteri fur iterative Naherungsverfahren zur Losung des Systems (1 ) seien die folgeriden genannt: Wenn die Startvektoren xo, . . . , xt E fJ bzw. xl, , r t E D vorgegeben sincl, wird der Vektor x') ' (n t , t 1 I , . . .) aus dcrn liriearcn Gleichungssystem

[

.

berechnet. Wahrend (7 ) zu den Verfahren vom Regula falsi-l'yp gSczahlt wird, grliort (8) zu den Verfahren vom SEWTON -Typ. Beide sind Mehrschrittverfahren.

bzw. 2. . . . , s" 1 in einer abgewandeltcn Reihenfolge in die Matrix h F eingehen lallt. Dazii sei (z. 76) die- jenipc naturlichc Zahl, welche bei festem t (lurch

Man kommt zu einer vom Aufwand her gunstigeren Variante, wenn man die Vektoren .Lii, . . . , . p I

(T . 1 1 ) = t (mod t ) uncl 71 - - t t 1 5 (z, n) 5 II (9) cindeutig festgclegt ist. LTnter den Zahlen a , / t - 1. , / I - f + 1 pibt es frirz = 1. . . , t inimer genau einc, wrlche pleicli (T . n ) ist

Vert'ahre'n Ntif Startvektoren: LO, . . . , 2 E 1) lterationsvorsclirift: Fu r rL = t , f + 1 , . Bestiminung von .F &US

qy') + ;3F(&."), . . , x(lA: x ( b - 1 , . . . , x(l,N)-l) (xll-t 1 - r?L ) = O

Dabei xei b F die Matrix (6) mit Spaltenvektoren der Form (3) oder (4)

V e 1. f a ti r e ii iM iY

Startvektoren. x1, . . , xt E D Iterationsvorschrift: Fur n = t , t 1, . . . Uestimmung von xn+l aub

> . . , & J O ) ( r e f 1 - ,T7') - 0 ( 1 1 ) Zq.z-7') $- dF(x(',%). . . . . J4 ,?&) : r(',a)

Hier ist 6F die Matrix (6) niit Spaltenvektoren der Form ( 5 ) . llas Verfahren M R f ist ein Mehrschrittverfahren vom Regula falsi-Typ, das Vcrfahrrn M N voni NBWWN-

TYP.

I) Die partiellen Ableitungen a,&', . . . , adJ' yon P' iriiigen existieren.

,I. CV. SCHMIDT: Uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und Newton-Typ 105

Um den Verlauf der Verfahren zu verdeutlichen, werden zum Verfahren MRf die Matrizen 6F fur die rrsten Schritte im Falle t = d = 3 explizit angegeben:

)1 = 3 . n = 4 hF(rr3, r2, r4; x2, xl, x3)

hF(x3,22: $1: x2, x1, x0)

/4 = .5. hF(x3. x5, x4; 9) x4, x3)

)/ - 6 hF(x6,25, x4: x5, x4, x3)

YL = 7: hF(x6, x5, x7: x5, x4, x6) . Man stellt allgemein bei den Verfahren M R f und M N fest, daB sich in der Matrix 6F fur t = d von Iterations- schritt zu Iterationsschritt jeweils nur eine Spalte andert. Das zieht nach sich, da5 man die Inversion in (10) bzw. (11) mit Vorteil nach der Formel von SHERMAN und MORRISON (s. z. B. [5]) vornehmen wird. Fur t < d iindert sich bis auf jeden t-ten Iterationsschritt ebenfalls nur eine Spalte in d F , wahrend es in jedem t-ten Schritt d - t + 1 Spalten sind. Bei der Inversion kann man dann auf die entsprechende Erweiterung der

Fur t < d ist es u. U. moglich, die Verfahren MRf und M N hinsichtlich der Inversion zu verbessern, indem man die Definition der Matrix 6F gegenuber (6) abwandelt. Als Muster werde dies fur d = t + m mit 1 < _ _ ?n 2 t vorgefiihrt. Fur ul, . . . , ut, vl, . . . , vt E D sei jetzt

SHERMAN-MORRISON-FOrmel zuruckgreifen.

hF(ut, . . . , ul; vt, . . . , v') = 6F(ut, vt; 1) dP(ut, vt; 2 ) . . . ~ F ( z L ~ - " + ~ , ~ l ~ - ~ % + l ; 2 m - 1) (12) I I

6F(u'-"+l, 2 m) GF(d-", wt-*l; 2 m + 1) . . . bF(ul, v l ; d ) , 1 I I I

[

d. h. die Vektoren u7, v' (t = t , t - 1, . . . , t - m + 1) werden jeweils zur Bildung von zwei Spalten verwendet, wiihrend u7, vt (t = t - m, t - nz - 1, . . . , 1) nur in eine Spalte eingehen. Von Interesse ist, daB die Bildung der Matrizen (6) uncl (12) mit der gleichen Zahl von F-Werten erfolgen kann. Die Matrix (12) ist jedoch gun- stiger, da sich von Iterationsschritt zu Iterationsschritt (bei der Annahme uber t) hochstens zwei Spalten andern und somit die Inversion in (10) bzw. (11) einfacher durchzufuhren ist.

Es seien einige weitere Verfahren erwahnt, welche mit dem beschriebenen Verfahren MRf eng verwandt sind. I te ra t ionsvorschr i f t : Fur n = t , t + 1 , . . . Berechnung von xn+l aus

6(@) + 6E"(z(t,-n), . . ., AM); y(tA, . . ., y(1.n)) (@+I - xn) = 0 . (13) 8;s ist dF die Matrix (6) (oder (12)) mit den Spaltenvektoren (3) oder (4), wiihrend die Vektoren 9% als

oder als

gewahlt werden (u > 0 konstante Zahl, e = (1, . . ., 1) E Bd). Bei Verwendung der Spaltenvektoren (3) sind diese Verfahren fur t = d von SCHWETLICK [9] angegeben und fur sie lokale Konvergenzsatze aufgestellt worden. Eine Ubertragung der Ergebnisse dieser Mitteilung auf die Verfahren (13) ist moglich.

y7~ == xn - 0 llrn - xx-111 e

yn = xn - u 11E"(z")11 e

3. Wirkungsgrad der Verfahren M f und MN

Die Verfahren MRf und M N enthalten bei fester Dimension d der Aufgabe (1) die Zahl t als Parameter. Es sol1 jetzt t mit Hilfe des Wirkungsgrades A = A ( t ) optimal festgelegt werden. Bekanntlich setzt man nach OSTROWSKI

), == xl la . (14) wenn x die Konvergenzgeschwindigkeit und (x den Aufwand an Funktions- und Ableitungswerten pro Schritt bezeichnen. Hier wird vereinfachend die Berechnung von F ( x ) , a,F(x), . . . , adF(x) jeweils als eine Funktions- wertermittlung gezahlt. Das optimale t = topt bestimmt man entsprechend der Forderung

A(topt) = max A(t) . t = 1 , ..., d

Die beiden Varianten des Verfahrens MRf werden jetzt mit MRl (Spaltenvektoren (3) in (6)) und M R 2 (Spal- tenvektoren (4) in (6)) unterschieden. Wie spater im Satz 1 gezeigt wird, ergibt sich ihre Konvergenzge- schwindigkeit einheitlich zu x = ItMRf(t) = XMRl(t) = ItMR2(t) als betragsgroote Losung der Polynomgleichung

(15)

(16)

X t t l - X t - 1 = 0 .

- xt-1 - 1 = 0 .

t f d

I m Verfahren M N wird diese KenngroBe x = xJfAr(t) gleich der betragsgrofiten Losung von

Fur den Aufwand a findet man durch Abzahlung als durchschnittliche Werte 2 ( t - 1) + d t + d

9 ~ M N =t t a M R 2 = S M R 1 =- t '

(z. B. benotigt man im Verfahren MR1 in t aufeinanderfolgenden Schritten insgesamt t + d Funktionswerte). 8

106 J. W. SCHMIDT: uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und Newton-Typ

Fur einige Dimensionen d sind diese GroBen in den Tabellen 1 und 2 zusammengefafit. Da13 der Unterschied zwischen einem Verfahren mit t = 1 und einem mit t = topt bemerkenswert sein

kann, werde am Verfahren M N fur d = 20 zahlenmaBig naher belegt. Bekanntlich ist fur die Gesamtzahl A = A(t) der benotigten Funktionswerte zur Erreichung einer bestimmten Geriauigkeit die asymptotische Beziehung

A( 1 ) : A(topt) M In A(t,,t) : In I,( 1)

gultig. Im erwahnten Beispiel ergibt sich

AAfN(1) :AMN(top t ) M 1,8:1 .

AuBerdem spricht fur die Verfahren mit t = top$ der geringere Aufwsnd bei der Auflosung des linearen Gleichungs- Systems (10) bzw. (11)) ermoglicht durch die SHERMAN-MORRISON-FO~~~~ ; dieser Antcil wurde durch 2 nicht erfal3t.

Wie man der Tabelle 2 entnimmt, unterscheiden sich bei den Verfahren MR1 und MCN die Wirkungs- grade fur t = d und t = topt in den angefiihrten Fallen nur wenig. Es liegt daher nahe, zumindest t = d und

nicht t = 1 in diesen Verfahren zu nehmen, d. h. Tabelle 1 man wird der Standardform der Regula falsi und Konvergenzgeschwindigkciten der Verfahren MRf und M N des NEWTON-Verfa hrens zumindest die Ver-

fahren M R 1 und M N mit t = d vorziehen. t xMRf(t) Z M N ( t -k 1) t ZMRf(t) = X M N ( t f 1) Das Verfahren JlRl hat auBer fur t = 1 1 1,6180 8 1,2131 und t = 2 einen grbReren Wirkungsgrad als das 2 1,4656 9 1,1975 Verfahren MR2. 3 1,3803 10 1,1843 4 1,3247 14 1,1469 Es sei noch erwiihnt, daB sich der Wirkungs-

grad durch fhergang zu sog. kombinierten Verfahren 5 1,2852 15 1,1400 (fur t = 1 beim Verfahren MR2 s. SCHMIDT und 6 1,2554 19 1,1187 SCRWETLICK [S]) weiter erhohen 1BBt. Diese Moglich- 7 1,2321 20 1,1145 keit wird hier nicht weiter verfolgt.

Tabelle 2. Wirkungsgrade der Verfahren MRf und Mh'

d Verfahren MRl Verfahren MR2 Verfahren MN

t = l In A( 1) t = l In A( 1) t = l In A( 1) t = d In l ( d ) t = d In A ( d ) t = d In d(d) t = t opt lnd(topt) t =: t opt Ind(topt) t = topt lnl(topt)

1 1 2 1

2 2

3 1 3 3

4 1 4 4

5 1 5 5

R 1 6 5

8 1 8 6

10 1 10 7

15 1 15 10

20 1 20 12

0,4812 0,1604 0,1911 0,1911 0,1203 0,1611 0,1611 0,0962 0,1406 0,1406 0,0802 0,1255 0,1255 0,0687 0,1137 0,1141 0,0535 0,0966 0,0975 0,0437 0,0846 0,0860 0,0301 0,0655 0,0677 0,0229 0,0542 0,0567

1 ,

1 2 1 1 3 1 1 4 2 1 5 2 I 6 3 1 8 3 1

10 4 1

15 6 1

20 7

0,4812 0,2406 0,1911 0,2406 0,1604 0,1381 0,1604 0,1203 0,1125 0,1274 0,0962 0,0965 0,1092 0,0802 0,0853 0,0967 0,0602 0,0703 0,0806 0,0481 0,0604 0,0703 0,0321 0,0457 0,0546

0,0241 0,0374 0,0457

1 1

2 1 3 2 1 1 3 1 .5 3

1 6 4

1 8 5

1 10 6

1 15 8 1

20 10

> i

0,3466 0,2311 0,2406 0,2406 0,1733 0,1911 0,1925 0,1386 0,1611 0,1638 0,1155 0,1406 0,1433 0,0990 0,1255 0,1289 0,0770 0,1043 0,1082 0,0630 0,0901 0,0941 0,0433 0,0685 0,0726 0,0330 0,0561 0,0601

J. W. SCHMIDT: Uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und N e w t o n -Typ 107

3. Konvergenzsatz fiir die Yerfahren MRf und M N im Banachraum

Es werden die Verfahren MRf und M N allgemein im BANAcH-Raum auf Konvergenz hin untersucht. Es wird ein Satz hergeleitet, welcher auBer uber Konvergenzbedingungen auch uber die Konvergenzgeschwindig- keit, die Existenz von Nullstellen und die Gute der Iterierten Auskunft gibt. Durch Vorgabe eines umfassen- deren Verfahrens kann dabei der Beweis fur beide genannten Verfahren gleichzeitig erbracht werden.

Es seien B ein BANACH-Raum, L(B) der Raum der linearen, beschrankten Operatoren von B in sich, PIC c B --). B ein nichtlinearer Operator und D c In t C eine konvexe Menge. Die Aufgabe bestehe in der Bestimmung eines x E D mit

F(s ) = 0 . (17) Rei Vorgabe einer naturlichen Zahl t sei ein Operator 6FID2t --f L(B) vorhanden, mit dessen Hilfe ein lterations- verfahren fur (17) wie folgt aufgestellt werden kann:

Ver fah ren M Startelemente: 2, . . . , xl, zo (= yl) E D Iterationsvorschrift: Bestimmung von xn+l fur n = t , t + 1, . . . aus der linearen Gleichung

F ( P ) + SF(dt,"), . . . , ~ ( ' 1 ~ ) ; y('sn), . . y('.")) ( x " + ~ - zn) = 0 .

yn = a, xn + (1 - a,) zn-l

(18)

(19)

Die Zahlen (t, n ) seien dabei durch (9) definiert. Fur die Vektoren y" gelte mit an E [ O , 11 2, .

Wenn at& = 1 fur alle n ist, entsteht bei entsprechender Wahl von SF dae Verfahren M N ; im Falle an = 0 fur alle n ergibt sich das Verfahren M R f , sofern man wiederum 6F geeignet festlegt.

Fur den Konvergenzsatz wird weiter angenommen, dal3 F eine FR&cHET-Ableitung P'ID --). L(B) besitzt und daB ein Operator F*IDt -+ L(B) mit

P*(zt. . . . , 21) = P ( z ) fur z = z1 = . . = zt c D (20) existiert. Es werde auBerdern fiir t = 1, . . . , t

IIry - x2-1 I I S b , ?

3 , = 0 . .y, -- ar 1 + 6, - vowie mit x, aus (19)

rl = 0 , r, = a, s, + (1 - a,) 8,-1

vereinbart. Damit folgen fur t = 1, . . . t

llz - x2-111 5 s, - s , _ ~ . I(x* - y"ll 2 s,- r , , IIy" - x2-111 5 r, -

Unter Bezugnahme auf diese (ausschliefllich im Abschn. 4 gebrachten) Bezeichnungen und Voraussetzungen kann das wesentliehe Ergebnis dieser Mitteilung formuliert werden.

S a t z 1 : Fur die S tar tehente xt. . . . . xl, xo (= yl) E D und zugehorige Elernente yt, . . . , y' gemtip (19) P.rintiwe dcr inverse Opwator

c: = 6P(xt, . . . , x': y'. . . . , yl)-' E L(B) . und cs gelte mit einer KoriPtantcn a > 0 fur uL, . . . . ul. d, . . . . ul, 2, . . . . z1 E D

t

\ l G { M ( u t , . . . . d: vt. . . . , u') - F*(zt. . . , zl)}ll 5 a 2 (Ilu' - zTll + 116 - ~ " 1 1 ) . (24) 2 - 1

2) Fur a1 + 0 folgt y1 = xl, so daB zwei der Startelemente ubereinstimmen; fur a1 = 0 ist y1 = xo. 8*

108 J . \V. SCHMIDT: Uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und N e w ton-l'yp

Weiterhin gelte fur die Kugel K K = {X E B: I I x - ~ ~ " 1 1 S * - b - C } c D ;

dabei se i _ _ ~~ 1

,q* - - ____ (1 + a @ - - v ( l + a P ) 2 - 4 ( 2 t - 1 ) a y } 2 ( 2 t - 1) a (29)

Unter diesen, Voraussetzungen i s t das Verfahren M durchfiihrbar, d . h. die Uleichungen (18) sind f u r alle ein- deutig nach x'L+l auflosbur, und der Grenzwert x* = lim xn ist vorhanden. Es ist F"(*) = 0. und ,wit x* E K steht eine Fehlerabschatxung xur Verfugung.

Gilt in Verscharfung von (27)

2 i ( 2 t - 1) a y < 1 + a p , (30) so erfolgt die Konvergenz uberlinear. Falls y n = 5" fur fast alle n ist, hat die Xonvergenzgeschwindig~eit mindestens den Wert x = xLTlis(t), wenn x,Ma( t ) die betragsgropte Losung der Pol~nomglei~hung

(31) ist. Andernfalls hat sie noch mindestens den Wert x = K M N (t + I ) .

Beweis: Dem Beweis des Satzes 1 werden der besseren tfbersichtlichkeit wegen mehrere Hilf'ssatze vorangestellt ; ohne besondere Erwahnung werden dabei seine Voraussetzungen iibernommen. AuSerdem werde zur Abkurzung z. B.

x t - - 1 = 0

u1 = (ut, . . . ~ ul) fur ut, . . . , u1 E B gesetzt,.

I-Iilfssat,z 1: Es seien

und Q = D Z t n E. Fulls (11~; bt) E Q ist, gilt fur den Operator H ( d ; b') == G {~F(U': b') - rJF(g'; 9')))

die Ungleichujig I

iiH(uC; uz))ll 5 a 2 (IIU* -- ~ * l l + 2 IIZJ* - X = I I + I I Z ~ - Y ~ [ I ) < 1 , t-1

und e;z existiert 8F(ut; U t ) - * = (1 + H(u'; b'))-l G E L(B) .

Keu eis : Unter Beachtung von (24) erhalt nian lH(U'; b')lI 5 IIG {BF(u'; b') - P*(b ' )}jI + IlG{F*(bt) - SE'(bt; a t ) 1 IjC: (c)E'(bt; z L ) - F*(x t )} , l i

t - I~( . ' ( / I ' " (x t ) - -SP(~t ;~ i t ) ) / / s u , Z ( j j u ~ - - ~ q 2:lc7 - T = I I 1 11.~7 y y ) < ' i

2 =1

Das BANacHsrhe Lemma iiber die Invrrsiori liriearer Operatoren sichert daher die Existenz von ( I 4 H ( n t ; bt))-l t L(B) und somit auch die von G F ( u ~ ; bt)-l E L(B) .

Hi l f s sa t z 2 : Es seien (m': 8') E D Z t und 1 5 v, p 5 t , soiiie u' -= tl(b'; 8': u+) m7i

R(mt; a t ; 7Lfi) = wfi - 8F(rot; a"-'F(w'P) vorhandm. Fulls dunn (u', b') E Q iht, existiert B(u'; b'; u'), und e

I

a { t (Iuy - wfilj + 2 (Ilu'l' - w l l + I I U P a21/)} IIuy 2 u q 2 1 1 IIR(ut; ut: u") - R(mt; g; rU" ) l l 5 t

1 - a 2 (IluT - vtlI f 2 l\v2 - xt(I 3- l1xz - yzllj) r = l

Beweis: Auf Grund der Definition von R ergibt sich zusammen mit Hilfssatz 1 R(ut; b'; uq - R(tUt; a t ; wfi) = R(ut; bl; u y ) - uy 7 - SF(11t; IJt)-' fquq

( I + H ( 1 ~ t ; bt))-' { G[F(u") - F(wP) - P'(t0'P) (?A' - TOP) I t G [ J " ( ~ f i ) OF( b t ; at) ] (Z IL

= - SF(u$; b')-l {F(uw) - P(u9fi) - SP(tUt; at) ( U Y - W) j _ - - N W ) ; .

Aus (20) und (24) folgt unniittelbar

IiG{F'(u) - B"(z)} l l 5 2 a t IIu - zlj fur u, z E D , so da13 die TAYLomxhe Formel angewendet werden kann:

IIG[F(uv) - F(TPP) - P'(w:P) (UY- wfi)]lI 5 u t 1 1 ~ ' - ~ 1 1 '

J. W. SCHMIDT: Uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und Newton -Typ 109

.\uBerclem ist wegen (24)

t ,IG[FI(wP) - SP(t-ot; a t ) ] (u” - W P ) \ ~ 2 u z ( I ~ w P - u>t-l[ + I ~ W P - ~ ‘ 1 1 ) 1 1 ~ ” - W P I I .

2 - 1

Wird noch (1 t H( ut; bt))-l mit den1 BANAcHschen Lemma abgeschMzt, entsteht die behauptete Ungleichung.

Hi l f ssa t z 3 : Uas puadratische Polynom

f ( s ) = u (2 t - 1) s2 - (1 + u p ) s + y

mit a > 0, @ 2 0 und y > 0 hat unter der Voraus,setzung (27) die Zahl s * aus (29) als kleinere Nullstelle. Die Itprationnfolqp (s7,) rntsprechend

rn+t = &,+I s,+i + (1 - & n + l ) s n , aEJ I E [O, 11 , (n = t , t + 1, . . .) und den Startwerten (22) konvergiert monoton wachsend gegen s *. Sofern (30) gi l t , hat die Konvergenzgeschwindig- keit i m Falle a, = 1 f u r fast alle n mindestens den Wert xMN(t), andernfalls ist sie noch nzindestens ( t + 1) (fur xMs( t ) 8. (31)).

neben st < s * auf Beweis: Die Ungleiehungskette st < - - < sn < S n + l < . . - < s* bestatigt man durch Induktion, wozu es genugt,

a ( 2 t - I) (8, + r E - t + l ) - (1 + a B ) < 2 a ( 2 t - 1) s* - (1 + a p ) = - t(1 + a p)z - 4 a (2 t --T$ 5 0 hinzuweisen. Somit ist lim s, = geschwindigkeiten ergeben sich fur an = 1 aus

a (2 t - 1) Isn - s * / ISn-t+l - s* j lSni-.l - s * ~ 5 ~ ~~~

l (1 + a p ) 2 - 4 a ( 2 t - 1) y

a (2 t - 1) 18% - S * l lSn-t - 8* j

t(l + a p y - 4 a ( 2 t - 1) y

(n 2 t )

5 s * vorhanden. Da weiter f (6”) = 0 gilt, folgt = a*. Die genannten ISonvergenz-

und andernfalls aus

.. lsnt1 - $*I 5 __ .

Hilfssatz 4: Die lineare Gleichung (18) ist fur n = t , t + 1, . . . eindeutignach xn+l auflosbar, und es gilt

(33) IIP+’ - znll 5 s n + l - 8% , )?zit 3% uus (32).

Beweis: Fur n = t existiert nach Voraussetzung 6P(gt; gt)-l, alsoauchxt+l, undes gilt I l x t + l - ztl/ Es gelte als Induktionsannahme (33) fur alle n 5 m - 1. Hieraus folgt / / x n - x t + l l l

c = s t + i - st. sn - ~ t + i 5 s* - b - c

und somit xn E K c D fur t + 1 5 n 5 m. Da nach Voraussetzung auch xo, . . ., x t E D sind, erhalt man xn, yn E D fur I 5 n 5 m . Es werden nun folgende Bezeichnungen vereinbart (m > t ) :

ut = (&,7n), . . .. z ( L m ) ) , bt = (y(t,m), . . ., y ( L 4 ) , uv = x m ,

tut = ( d t , r n - l ) , . . .) x(l ,wL-l)) , at = (y(t,m-1), . . .) y ( l , m - l ) ) , WP = z7n-l . Damit gelten (t-ot; at) E Dzt, (ut; bt) E D2t und nach Induktionsannahme ist uv = R(W; a t ; WP) vorhanden. Beachtet man weit’er die leicht zu bestatigenden Ungleichungen jlxn - ynll 5 sn - r , und llyn - x n - l / j 5 rn - Sn-1, so wird fur ut, bl

t t

r = l r = l z (lid7.m) - ~ ( T J ~ I + 2 ~ly(t-,m) - x q + 1 1 % ~ - y q ) 5 u ( s ( ~ , ~ ) + r(t,m) - s7- rt-)

t t -1 t

t=l t=l t-=2 == u z ( s m - - t + t + ~ , n - t + r ) - u /3 =z u (8, + ~ m - t + l ) + u 2 ~ m - - t + 7 + u rrn-t+r - u B

j a ( 2 t - l ) ( s m + r w L - t + i ) - u P < 2 a ( 2 t - 1 ) s * - aj3 5 1 .

Diese Ungleichung bedeutet aber (ut; bt) E E und folglioh (ut; bt) E &. Somit ist der Hilfssatz 2 anwendbar. Er sichert die Existenz von z m + l = R ( 3 ; bt; u v ) und die Abschatzung

t a t 11xm - xm--1[j + (1!2”-1 - &,m-1)1\ + 11xm-l - y( r,m-l)ll)} 1jzm - xrn--l lI I -_ 7 = 1

l l x m + l - Z q 5 t 1 - a z ( ~ l ~ ( a , m ) - y(7,m)l! + 2 lly(t-m) - 41 + llxt- - y”II)

t-=l

Wahrend fur den Nenner eben bestLtigt worden ist, dal3

1 + a p - a ( 2 t - 1) (8, + mm-t+1)

110

eins untere Schranlte ist, wird dw Zahler nach oben nbgeschatzt durch

J. TV. SCHMIDT: Uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und Newt on-Typ

t

t - 1 ( S 7 n s I l 1 1) + (2 h ? ) f I \ (T .W 1 ) rh.W! 1)) } (Sm -- STII 1 )

S ( z { t s J n t ( t - l ) s n - i - ( 2 t - l ) r ~ - t ) ( s ~ ~ - S V - I )

5 a (2 t - 1) (sn& - s, 1 ) ( s , - rwt - t ) . lnsgesamt ergibt sich als -4bschlu13 des Beweises zunl Hilfssatz 4

Die Ungleichung (33) des Hilfssatzes 4 impliziert zusammen mit der im Hilfssatz 3 nachgewiesenen Konver- genz der Zahlenfolge (s,), dalj (3) eine CAuCHY-FoIge ist und somit wegen der Vollstandigkeit yon B der Grenz- wert x* = lim ,rn existiert. AuDerdem folpt die zur Angabe der Konvergenzgeschwindigkeit niitzliche Un- gleichunp

fur n = t + 1 bedeutet sie, dalj x* E K ist. jlz* - ~ 7 ~ 1 1 I - s * - A , 6 . ( tb I , 2 , . . .) :

Schlieljlich ist x* eine Nullstelle von P, denn auf der rechten Seite von (fur u', b' x . Hilfssatz 4) F ( x * ) = [F(x*) - F(x") - F ' ( P ) (x* - x")] + [{P'(z") - bF(Ut; b')} ( x * -. x " ) ] f

+ [ { G F ( U t ; b') - F'(X*)} (x* - x " ' - ' ~ ) ] + [P'(X*) (x* - Xm+')l streben die Ausdriicke in den eckigen Klammern fur m -+ 00 gegen Null. Damit ist der Beweis des Satzes 1 vollstandig.

5. Eine Verseharfung dor Fehlerabschatzung

Es wird mit der Ungleichung (39) auf eine Moplichkeit hingewiesen, die im Satz 1 angegebene Fehlerabscahat- zung :r* E K , d. h.

fur die nach dem Verfahren ill bererhnete Iterierte xtL zu verbessern. Gleichzeitig wird die Voraussetzung (24) aufeelockcrt. Fur manche speziellen Verfahren M ist es angepaBter, an ihrer Stelle lediglich

jlx" - X t ' 111 5 s" -- b - t (34)

t IlQ{hF(ut, . . .. i d 1 : c t , . . ., u') - F*(z'. . . ., z1))l l 5 2 (a l , llur - z ~ I I + a2t (16 - z'll) (35)

t= 1

zu fordern (al , 2 0, aZT 2 0 Konstanten: II', uz, zT E L, beliebig (t = 1. . . . , t ) ) . Es wird angenommen, daB mit n pt.niiilj

die Voraussetzungen voni Gatz 1 erfullt sind, so dalj zunachst einmal die Abschatzung (34) gesichert ist. Urn sie zii verhessern. wird eine Zahlenfolge (&) eingefuhrt :

0 CClt, a2r 5 u fur t = 1. . . . ) t (36)

t - Z ( a l r + ~ Z r ) ( S n - f l v , - - ~ ) ' + 2 [ a i r ( S , - , -~S( t , s - i ) )+azr ( sn ~ - ~ ( T , , ' - ~ ) ) l ( S n - s , C - - l ) ~ 1 r 2 t = l T = I

1 1 - G lalr(%,n) - &,d + ( U l r + %t) (R(t,n) -

I = a n - I &+I + (1 - 01,

t a 2 r (8, - &)I r:l

(72 = t + 1 , t + 2 , . . . ) , R, == 0, En

llzn' -- F l l 5 S B f l - s, (= s, L 1 -- s, ,

1) Sn, and 1 E [0,1],

(n = t , t $- 1 , . . .)

(n = 1.2, . . .). lndem inan den Beweis zum Hilfssatz 4 verfolgt, stellt man nach einigerl Zwischenrechnunpen fest. tlaW

(38) gilt. Wegen St+, = 8t+l = b + c (b aus (23 ) ) ergibt sich also S, 5 &., < s*. k'olglich besitzt (8,) einen Grenzwert S* = lim S,, und es ist S* 5 s*. Wahrend fur s * mit (29) eine Formel zur Verfiigung steht, durfte A * i. a. nicht explizit angebbar sein. Man wird vielmehr unmittelbar auf die Rekursionsformeln (37) zuruckgehen, wenn man S* zu berechiien hat.

s,

Wie im Beweis zum Satz 1 erlautert worderi ist, erhalt Inan ails (38) / IT* - XfLII 5 A* - s, 5 A * - sn:

I jX * - X t + l l l 5 8" - b - c . fur n = t + 1 ergibt sich als Verscharfung von (34)

(39) Die Abschatzung (39) ist gultig unter den Voraussetzungen des Satzes 1, wobei noch die Forderung (24) durch (35), (36) abgeschukicht werden kann.

J. W. SCHMIDT: Uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und Newt on -Typ 1 1 1

Die Voraussetzung (27) dient im Grunde nur zur Sicherung der Konvergenz der Folgen (s,) und (S,). Daber genugt es im Hinblick auf die Abschatzung (39), an Stelle von (27) abschwachend zu fordern, daB die Folge (8,) gebildet werden kann - die Nenner in (37) seien stets positiv - und da13 sie gegen eine Zahl S* konvergent ist. Man hat dann in der Definition (28) der Kugel K noch s* durch S* zu ersetzen.

6. Eindeutigkeitssatz

S a t z 2 : Die Voraussetzungen des Satzes 1 seien erfiillt. Mi t den dortigen Abkurzungen und mit

werde irn Falle s * < s * * M = {X E B : I I x - ~ ' 1 ) < a * * - b }

und irn Il'alle s * = s * * M = {X E B : 1 1 % - x ' I ] 5 s* * - b }

gesetxt. Dann hat P i n D n M aufler X* keine weitere Nul l~ te l l e .~ ) Beweis: Es sei z E D n H eine Nullstelle von P. Dann gilt

wobei fur s* < s** die Ungleichung s* 5 5 < s** angenommen werden kann; fur s* = s** kann 5 = s* gesetzt werden. Wie im Hilfssatz 3 zeigt man fur die Iterationsfolge

llz - ztll 5 5 - St 9 (40)

daO lim 5, = s * ist. Die Iteration -= Z, z n + l = zfi - GF(dQ0, . . ., d W ; y ( W , . . ., @,))-1 F(zn) , (n = t , t + 1, . . .)

fuhrt wegen H(z) = 0 auf eine stationare Folge mit dem Element z. Wie anschlieBend durch Induktion nachgewiesen wird, besteht die Ungleichung

aus welcher im Sinne der Behauptung z = lim zn = z* folgt. Fur n = t ist (41) wegen (40) gultig. Falls (41) fur alle n 5 112 vorausgesetzt wird, erhalt man wie im Hilfssatz 2 uber (u', bt siehe Hilfssatz 4)

die Ungleichung

J jzn - z,\/ = llz - znjl 5, - s,, (n = t, t + 1,. . .), (41)

znz+1 - zm+1 = - GF(ut; bt)-l {Pfzm) - F(z.2) - 6F( ut; bt) (2" - z"))

t a t llzm - z m l / + 2 (Ilzm - z(m)ll+ ljzm - y(w)ll)} 1/zm - zmll

T = 1

t

r = l 1 - a (I]z(rm) - y(r,m)ll + 2 Ily(r,m) - + IIf l - ~ 1 1 )

l (zm+l - zm+lll 5 - 1 t

a 1 ( ~ m - sm) + ,Z ( 2 sm - s(r,m) - r(r,m)) ( ~ m - 8%)

< - . ~ _ _ _ _ ~ _ r = l . -- __ 1 - t - -

1 - a 2 (s(t,m) + r(r,m) - ST - TT) r= l

Fur 7n = t wird der Nenner bei der ersten Abschitzung gleich 1 2 1 + a B - a (2 t - 1) st > 0. Damit ist der Induktions- beweis vollstiindig.

7. Einige Sonderfllle vom Satz 1

Aus dem Satz 1 kann man durch Spezialisierung den grundlegenden Satz von KANTOROVICH uber das NEWTON- Verfahren erhalten. Ebenso ist es moglich, einen analogen Satz uber die Regula falsi zu gewinnen.

Wie im Abschn. 4 seien B ein BANAcHraum, L(B) der Raum der linearen, beschrgnkten Operatoren von Bin sich und F ( C c B -+ B ein Operator, welcher aufeiner konvexen Menge D c In t G eine FRkCHET-Ableitung F'ID + L(B) besitzt. AuBerdem existiere ein Operator 6FIDZ --f L(B). Dann gilt uber die Regula falsi

P ( P ) + 6F(xn; x"-l) (xn+l - xn) = 0 , ( n = 1 , 2 , . . .) (42) der folgende

vorhanden, und es gelte rnit einer Konstanten a > 0 S a t z 3 (s. [2], [?I): Fur die Startelemente xl, xo E D sei der inverse Operator G = 6F(x1; x0)-l E L(B)

IlG{GP(u; v) - P'(z)}ll 5 a (Ilu - z]I + Ilv - z l ] ) fur u, v, z E D .*) (43)

3) Wegen K c M und K c D ist die nach dem Satz 1 vorhandene Nullstelle x* E K in D n M gelegen. 4, SF heiSt zu F' konsistent, wenn (43) erfullt ist (8. [5]) .

112 J. W. SCHMIDT: Uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und N e w t on-Typ

N i t llxl - xnll 5 b und 11x2 - xlll 5 c sei ~ _ _ _

2 l / a ( b + c ) S l + a b erfullt. Weiterhin gelte

mit der d bkurzung 1

2 a

K = {x E B: 11.1. - x211 5 s * -- b - c } c 1)

s * = - { 1 + a b - 1/(1 + a b ) 2 - 4 a (b + c ) ] .

Unter diesen Annahmen ist die Regula falsi (42) durchfuhrbar. Die Polge (x)’) ist gegen eine NullstelleIr* von F konvergent, und es gilt x* E K. I m Palle 2 l a ( b + c ) < 1 + c( b erfolgt die Konvergenx naindestens wit der Geschwindigkeit (1 + 15)/2.

nugt der Hinweis, daD dann in (23) b = B und in (26) y = b + c werden.

-~

Beweis: Mit a, = 0 fur alle n geht die lterationsvorschrift (18), (19) in (42) uber, wenn t - 1 gesetzt wird. Es ge-

Falls an Stelle von (43) die Forderung

IIG(GF(u, v) - F’(z))ll 5 a, IIu - z I I + a2 IIz1 - 211 fur u, v, z E D angepaBt ist, laBt sich die mit x* E K gegebene Fehlerabschatzung noch verbessern. Hierzu sind die Ergebnisse des Abschn. 5 umzusetzen.

Wahlt man 6F in der speziellen Form

und setzt man a, = 1 fur alle n sowie t = 1, entsteht aus der Vorschrift (18), (19) das NEwToN-Verfahren: F(x“) + F’(xn) - x”) = 0 . (n = 1, 2, . . .) , (45)

S a t z 4 ( K a n t o r o v i c h ) . Fur dasStartelement x1 E Dexistiere C = F‘(xl)-l E L(B). Mit einer Konstanten a > 0 gelte

Es bestehe mit ]It2 - xlll 5 c die Ungleichung

Setzt ma17

IlC{F’(u) - B”(z)}jl 5 2 a IIu - 211 fur u, z E D . (46)

4 a c 5 1 .

-__- 1 2 a

s * = - - ( I - 1/1 - 4 a c ) .

70 gelt? fur die Kugel K K = {X E B: ~ I . L -- x211 5 s * - C } c D .

Unter diesen Voraussetzungen ist das N e w t o n - Verfahren (45) durchfuhrbar. Die Folge (x’l) konvergiert gegen e k e Nullstelle x* won F , und es ist x* E K . I m Falle 4 a c < 1 erfolgt die Konvergenx mindestens quadratisch.

B e weis: Man setze t = 1 und an = 1 fur alle n. Es werden dann in (23) h = - 0 und in (26) ̂ J = c. Der Operator b7Q gemaD (44) erfullt auf Grund von (46) die Voraussetzung (24).

Es sei erwahnt, daB den Satzen 3 und 4 mit Hilfe der Ergebnisse vom Abschn. 6 noch Eindeutigkeits- aussagen angrfugt werden konnen .

8. Voraussetzung (24) fur die Verfahren MRf und MiV im Rd Es bedarf keiner zusatzlichen Bcmerkungen, wenn es um die uberprufung der Voraussetzungen zum Satz 1 geht. Eine Ausnahme bildet lediglich die Forderung (24). Es ist von Interesse, hinreichende Redingungen fur (24) und ihre Abschwachung (35) zur Verfiigung zu haben.

Der Raum Rd, in dem eine derartige Bedingung hergeleitet werden soll, sei durch die Maximum-Norm normicrt ; die zugeordnete Norm im L( Rd) ist die Zeilensummen-Norm. Es seien F ( C c Rd -+ Bd der Operator, dessen Nullstellen zu ermitteln sind, und GIRd -+ Rd der im Satz 1 genannte lineare Operator. Fur D c Int C wird zur Vereinfachung ein achsenparalleler Quader genommen.

Wahrend die Matrix d F durch die Gleichung (6) erklart sei, ist hier als F * folgrnde Matrix geeignet:

(47) .

F*(zt, . . . , zl) = a J ( 2 t ) . . ‘ a d - - t + l F ( Z t ) a, 1 F.zF(zt-1) . . . [ I Man stellt fest, daB G‘ d P = d(G F ) und C F* = (G F ) * zutreffen. l m Qrunde sind tlaher (24) und (35) For- derungen an den Operator G F . Es sei G F = ( f l , . . . , id) ; die Funktionen f z l C c Rd -+ !R1 (i = 1, . . . , d ) mogen differenzierbar sein und die Ableitungen LIPscHITz-Bedingungen erfullen :

la,fl(u) - a,fl(z)l 5 2 azlcl J u t - z71 fur u = (ul, . . , ud) E I ) , z = (2,. . . . z d ) c 1) d

3-1 (48)

J. W. SCHNIDT: ifberlinear konvergente Mehrschrittverfahren vom Regula falsi- und New ton-Typ 113

( k = d - t + + , . . , d ) 1 < r ~ r l s : Die SpaJtenvektoren van 'sP mogen die Form (3) hsben. Dann wird

I cJ{GF(ut, . . ., 9 2 ; d, . . .) c1) - F*(z l , . . ., Z 1 ) ) l l =

t- 2 niax Ibfi(ud-b t 1 , ~d h - 1; k ) - a k f i ( z d - k t l ) l . k = d - t + 2 % = I , ..., d

so dall nlan durch Einsetzen von (49) unmittelbar die Unglvichung (35) mlt den Konstanten (51) bekommt. Ebenso zeigt, man unter Verwendnng van (50) den zweiten Teil des Satzes.

Urn das Verfahren iVN zii erhalten. setzt man mit F* ails (47) (vergleiche auch (44))

(53) 1 2

hF(ut , . . .. 7d; vt. . . ., v') = --{F*(ut, . . .: u 1 ) -k E'*(wt, . . ., v"} .

Sa tz 6 : Werden die Lip,schitz-BedingzLngen (48) vorausgesetzt, erfullt die Matrix (53) 6% Ungleichungenj (35) und (24) niif

J 1 d- l -c l rl 1

( k = m

alt = u ~ t = -- max 2 2 a i k j , a l , d - k f l = a B , d - k + l = - max 2 uikl ,

t + 2 , . . ., d ) .

2 i=l , ..., d k = l ,j=1 2 i=l, ..., a j = l

(54)

114 J. W. SCHMIDT: uberlinear konvergente Mehrschrittverfahren vom Regula falsi- und New ton-Typ

Heweis: Es ist

1 2 7 IICr'{P*(wt,. 1 .. c'i - F*(z$. . . ., z q l ! ;

weiter wird f/-t;1

Bei Beriicksichtigung von (48) folgt hieraus die Behanptung.

9. Numerisches Reispiel Als nichtlineares Gleichungssystem wird jenes genommen, welches aus der Randwertaufgabe

.d' = (1 + 2 t + 3 t 2 + 4 t3 ) (6 + 3 x - 4 x2 + x3) , ~ ( 0 ) = ~ ( 1 ) = 0 durch Anwendung des Mehrstellenverfahrens bei der Schrittweite h = 1/10 entsteht. Es handelt sich also um 9 Gleichungen mit ebenso vielen Unbekannten, d = 9. Verglichen wird das Verfahren MRf (lo), (4) fiir die beiden Falle f = 1 (Regula falsi) und t = 9 (Mehrschritt-Regula falsi), wobei als Startvektoren fur t = 1 die Vektoren xo und x1 mit (xO), = - 1.0 und (d), = - 0.9 und im Fall t = 9 die Vektoren ~ - 8 , 2 - 7 , . . . , x1 mit ( x ~ ) ~ = - 1.0 fur i 5 1 - z und (xZ)$ = - 0.9 fur i > 1 - z (i = 1 , . . ., 9; z = - 8, - 7 , . . ., 1) ge- wiihlt werden. Den Verlauf der Iteration geben die Tabellen 3 und 4 wieder; als Muster wird jeweils die Komponente ( . E ' ' ) ~ von 1'' genannt,.

' rabelle 3. Verfahren M4f Tabel le 4. Verfahren MRj' mit mit t - 1 (Regula falsi) t = 9 (Mehrschritt-Regula falsi)

fl (27% n (2%

2 -0.781 259 294 928 3 - 0.756 824 270 390 4 -0.753 842 642 398

6 - 0.753 789 248 239 5 - 0.753 789 340 985

2 3 4 5 6 7 8 9

10 11

-0.781 259 294 928 -0.760 073 930 966 -0.755 096 123 128 -0.754 029 708 612 - 0.753 828 255 858 -0.753 794 546 431

-0.753 789 341 399 -0.753 789 256 500 -0.753 789 248 246

-0.753 789 977 948

ZunBchst erkennt man die geringere Konvergenzgeschwindigkeit der Mehrschritt-Regula falsi im Ver- gleich zur Regula falsi. Betrachtet man jedoch den Wirkungsgrad, so fallt der Vergleich deutlich zugunsten der Mehrschritt-Regula falsi aus. Wahrend im ersten Schritt bei beiden Verfahren 10 Funktionswertberech- nungen erforderlich sind, benotigt man im Fall t = 1 fur die weiteren Schritte insgeaamt 36 und im Fall t = 9 insgesamt nur noch 25 Funktionswerte. Es ergibt sich also fur den in Funktionsberechnungen gemessenen Gesamtaufwand ein Quotient von 36:25 = 1.44:l (bzw. 46:35 = 1.31: 1) . Dieser steht ungefilhr im Ein- klang mit dem asymptotischen Wert 1.21 : 1, den man nach den im Abschn. 3 beschriebenen theoretischen uberlegungen erhalt.

Literatur 1 BITTNER, L., Eine Verallgemeinerung des Sekantenverfahrens zur ngherungsweisen Bereohnung der Nullstellen eines

nichtlinearen Gleichungssystems. Wiss. Z. Techn. Univ. Dresden 9, 325 - 329 (1959). 2 BURMEISTER, W., Inversionsfreie Verfahren zur Losune: nichtlinearer 0Deratore:leichune:en. ZAMM 32. 101 - 110 (1972). 3 DANILIN, Ju. M. und PBENIENY~, B. N., Uber Minirnier&gsmethoden mit' beschlzunigterkonvergenz (russ.). 2. vyEii1. rnaf.

i mat. fiz. 10, 1341-1354 (1970). 4 KORGANOFF, A., MCthodes be Calcul NumBrique. Paris 1961. 5 ORTEGA, J. M. and RHEINBOLDT, W. C., Iterative solution of nonlinear equations in several variables. New York-Lon-

6 SCHMIDT, J. W., Eine ubertragung der Kegula falsi auf Gleichungen in Hanachraumen. ZAMM 41, T61-T63 (1961) und

7 SCHMIDT, J. W., Regula-falsi-Verfahren mit konsistenter Steigung und Majorantenprinzip. Periodica Hung. (im Druck). 8 SCHMIDT, J. W. und SCHWETLICK, H., Ableitungsfreie Verfahren rnit hoherer Xonvergenzgeschwindigkeit. Computing 3,

9 SCHWETLICP, H., Uber die ReaIisierung und Konvergenz stabiler Mehrschrittverfahren zur iterativen Losung nichtlinrarer

Eingereicht am 20. 3. 1972

An8Chrift: Prof. Dr. J. W. SCHMIDT, Technische Universitat Dresden, Sektion Mathematik, 8027 Dresden, Zellescher Weg

don 1970.

ZAMM 43, 1-8, 97-110 (1963).

215-226 (1968).

Gleichungen (in Vorbereitung fur die ZAMM).

12-14, DDR