C H A P T E R
Systems ofNonlinear Equations
10.1 Introduction
Alarge partofthematerial inthisbook hasinvolved thesolution ofsystems ofequations .
Even so,tothispoint themethods have been appropriate only forsystems oflinear equations ,
equations inthevariables xi,x2,...,xnoftheform
at\X\+ai2x2+   +ainxn=b{
fori=1,2,...,n.Ifyou have wondered why wehave notconsidered more general
systems ofequations ,thereason issimple .Itismuch harder toapproximate thesolutions
toasystem ofgeneral ,ornonlinear ,equations .
Solving asystem ofnonlinear equations isaproblem thatisavoided when possible ,
customarily byapproximating thenonlinear system byasystem oflinear equations .When
thisisunsatisfactory ,theproblem must betackled directly .Themost straightforward method
ofapproach istoadapt themethods from Chapter 2thatapproximate thesolutions ofasingle
nonlinear equation inonevariable toapply when thesingle -variable problem isreplaced
byavector problem thatincorporates allthevariables .
The principal tool inChapter 2wasNewton ’smethod ,atechnique thatisgenerally
quadratically convergent once asufficiently accurate starting value isfound .This isthe
first technique wemodify tosolve systems ofnonlinear equations .Newton ’smethod ,as
modified forsystems ofequations ,isquite costly toapply ,so,inSection 10.3,wedescribe
howamodified Secant method canbeused toobtain approximations more easily ,although
with alossoftheextremely rapid convergence thatNewton ’smethod provides .
Section 10.4 describes themethod ofSteepest Descent .This technique isonly linearly
convergent ,butitdocs notrequire theaccurate starting approximations needed formore
rapidly -converging techniques .Itisoften used tofindagood initial approximation for
Newton ’smethod oroneofitsmodifications .
InSection 10.5,wegiveanintroduction tocontinuation methods ,which useaparameter
tomove from aproblem with aneasily determined solution tothesolution oftheoriginal
nonlinear problem .
Asystem ofnonlinear equations hastheform
/l(*l.*2.   ,X n)=0,
MX\,x2,   1x„)=0,
f n(X|»X2t...9X f i)—0,
where each function fcanbethought ofasmapping avector x=(xj,x2t...,x„)1of
then-dimensional space R”intothereallineR.Ageometric representation ofanonlinear
system when n=2isgiven inFigure 10.1.
413
Copyright 20I2Cengagc Learning .AIR.ghu Reserved May rscabecopied .scanned .orduplicated .'»whole ormpan.Doc toelectronic rights .tone third party concent nu>besupprcsxd Trent theeBook and/oreChaptcnM .Editorial review h*>
deemed tutany vupprc'-cdcontent dee *,notmaterials affect theoverall learning experience .Ceng ageLeant ngreverses theright torerrx'sradditional conceal atanytime ifsubvcijjcti nglas restrictions require it.414 CH A PTER 10 Systems ofNonlinear Equations
Figure 10.1
Z=Mxl,x2)
z=/,(*„*2)
I
*2
/I(XI,x2)=0and/2(xi**2)-0
*1
Ageneral system ofnnonlinear equations innunknowns canbealternatively repre -
sented bydefining afunction F,mapping R"intoR",by
F(*1.*2 X n)=(/l0*1.*2 *„)M*\*2 */>) M*l,x **))' 
Ifvector notation isused torepresent thevariables x\,x2,...,xn %thenonlinear system
assumes theform
F(x)=0.
Thefunctions /1,/2,...,/„ar eth ecoordinate functions o fF.
Example 1Place the3x3nonlinear system
1-COS(*2*3)“-
x2—81(JC2+0.1)24-sin;t34-1.06=0,
10;r—33JCJ =0,
e*1*2_
j_20x34- =03
intheform F(x)=0.
Solution Define thethree coordinate functions /1,/2,and/3from R3toRas
1Mxi ,x2,xj)=3A:1—cos(x2X3)-
fiixuX 2%xi)=x]-81(JC24-0.1)2+sin*34-1.06,
107 T—3Mxux 2,A:3)=eX'X24-20A:34-3
Copyright 2012 Certfajc Learn in*.AIRights Reserved Mayr*xbecopied.scanned .ocdedicated.»whole oempan.Doc 10electronic rights.some third pony concern.may besuppreved riom theeBook and/wcCh<xcn»l.Editorial review h*>
deemed Cutanysuppressed content does notmaterial yalTcct thei>vera'.llearning experience .Cettgagc [.camonreserves theright toremove additional conteatatanytime ifsubsequent rights restrictions require IL415 10.1 Introduction
Then define Ffrom R3—R3by
F(x)=F(jr,,JT2,x3)
=(/l(*i.x2,*3).h(x\,x2,x3),f3(x,,x2,x3))'
=(3*1-cos(*2*3)-L x
10r1)']-81(JC2+0.1)2-I-sin JC3+1.06 ,e’*1*2+20x3
Theoriginal system isequivalent toF(x)=0.
Before discussing thesolution ofasystem ofnonlinear equations ,weneed some results
concerning continuity anddifferentiability offunctions from R"intoRand Rninto Rn.
These results parallel those given inSection 1.2forafunction from RintoR.
Let/beafunction defined onasetDcR"andmapping R”intoR.Thefunction /
hasthelimit LatXo,written
lim/(x)=L,
X-**U
if,given anynumber e>0,anumber 8>0exists with theproperty that
|/(x)-L\<e whenever xeDand 0<||x—XQ||<8.
Any convenient norm canbeused tosatisfy thecondition inthisdefinition .Thespecific
value of8willdepend onthenorm chosen ,buttheexistence andvalue ofthelimit Lis
independent ofthenorm .
Thefunction /from R"intoRiscontinuous atxo Dprovided limx-»xo/(x)exists
andis/(x0).Inaddition ,/iscontinuous onasetDprovided /iscontinuous atevery
point ofD.This isexpressed bywriting /eC(D).
Wedefine thelimit andcontinuity concepts forfunctions from R”intoR"byconsidering
thecoordinate functions from R"intoR.
LetFbeafunction from DCR"intoR”andsuppose Fhastherepresentation
F(x)=(/i(x),/2(x)/„(x))',
where/,isafunction from R"toRforeach i=1,2,...n.Wedefine thelimit ofFfrom
R"toR"as
limF(x)=L=(Li,L2,...,Ln)‘
Continuity definitions for
functions ofnvariables follow
from those forasingle variable
byreplacing ,where necessary ,
absolute values bynorms .ifandonly iflim*-^/)(x)=L,foreach i=1,2,...,n.
Thefunction Fiscontinuous atXoGDprovided lim
addition ,Fiscontinuous onthesetDifFiscontinuous ateach xinD.
These arethebasic concepts wewillneed fortheremainder ofthechapter .F(x)exists andisF(xo).InX-*-*o
Copyright 2012 Cc«£»fcLearn in*.AIR.(huReversed May notbecopied ,canned ,o*duplicated.»whole otmpan .Doctoelectronic rifhu.vontc third pony content may bevuppreved Trent theeBook and/orcCh<xcn»l.Editorial roiew h*>
deemed Cutanyvuppicwcd content dec*notimtetlaly alTcct theoverall Icamir .itexperience .Cc»i|tape[.cannon rexxvcv therljtlu 10renxyve additional conteatatanytime iivutoeqjcni nphtv restriction*require It416 C H A P T E R 1 0 Systems ofNonlinear Equations
10.2 Newton 'sMethod forSystems
Newton ’smethod forapproximating thesolution ptothesingle nonlinear equation
fix)=0
requires aninitial approximation potopandgenerates asequence defined by
f(P k-i)
f(p k-i)’fork>1. Pk=Pk-1-
Tomodify Newton ’smethod tofindthevector solution ptothevector equation
F(x)=0,
wefirstneed todetermine aninitial approximation vector p(0).Wemust then decide how to
modify thesingle -variable Newton ’smethod toavector function method thatwillhave the
same convergence properties butnotrequire division because thisoperation isundefined
forvectors .Wealso need toreplace thederivative of/inthesingle -variable version of
Newton ’smethod with something thatisappropriate forthevector function F.
TheJacobian Matrix
The derivative /'(*)ofthesingle -variable function /(*)describes how thevalues ofthe
function change relative tochanges intheindependent variable x.The vector function Fhas
ndifferent variables ,x\9*2»   >xnyandndifferent component functions ,/i,/2,...,/n,
each ofwhich canchange asanyoneofthevariables change .Theappropriate derivative
modification from thesingle -variable Newton ’smethod tothevector form must involve all
these nlpossible changes ,andthenatural waytorepresent n2items isbyannxnmatrix .
Each change inacomponent function fatxwith respect tothechange inthevariable xj
isdescribed bythepartial derivative
V(x),dxj
andthenxnmatrix which replaces thederivative thatoccurs inthesingle -variable case is
d f i,va/, a/.(x) (x)    (x)
dxi dx2 dxn
a/2 a/2 a/2(x)    7^(X) (X)
dxi dx2 dxn
Thematrix J(x)iscalled theJacobian matrix andhasanumber ofapplications inanalysis .It
might ,inparticular ,befamiliar duetoitsapplication inthemultiple integration ofafunction
ofseveral variables over aregion thatrequires achange ofvariables tobeperformed .
Newton ’smethod forsystems replaces division bythederivative inthesingle -variable
case with multiplying bytheinverse ofthenxnJacobian matrix inthevector situation .
Asaconsequence ,Newton ’smethod forfinding thesolution ptothenonlinear system of
equations represented bythevector equation F(x)=0hastheform
P<*>=P(*_,)-Uip(*-I))rlF (P(*-I>),
given theinitial approximation pimtothesolution p.^(x)...3f'^(x)dx2 dxn
fork>1,
Copyright 2012 Cenfajc Learn in*.AIR.(huRocncd May n«becopied ,canned ,o*implicated ,inwhole orinpar.Doctocjectronie rifhu.*wcthird pur.ycontent may besupplied rican theeBook and/orcChaptcnM .Editorial roiew h*>
deemed CutanyMpprccscd content dce>notnuetlaXy afTcct theoverall learnire experience .Cenitape [.camon roenti theright Mremove additional conceal atanytime i!vuhvcyjcm nghtv rotrictiots require It.417 10.2 Newton 'sMethod forSystems
Aweakness inNewton ’smethod forsystems arises from thenecessity ofinverting
thematrix J{p{*-,))ateach iteration .Inpractice ,explicit computation oftheinverse of
y(p(*-0)isavoided byperforming theoperation inatwo-stepmanner .First,avector y(*-,)
isfound thatwillsatisfy
Theprogram NWTSY 101
implements Newton ’s
method forsystems of
nonlinear equations .J(p<*-,))y(*“,)=—F(p(*-1)).
After thishasbeen accomplished ,thenewapproximation ,p(*\isobtained byadding y(*_,)
top(A_
I).
Example 1Thenonlinear system
13*1-cos(*2*3)-2
*f-81(*2+0.1)2+sin*3+1.06=0,
IOTT-3=0,
+20*3+ =03
hastheapproximate solution (0.5,0,-0.52359877 )'.Apply Newton ’smethod tothisprob-
lemwith p(0)=(0.1,0.1,-0.1)'.
Solution Define
F(*i,*2»*3)=(/l(*l,*2,*3),/2(*1.*2.*3),M*UX2,Xi)y,
where
1/l(*l,*2,*3)=3*1-cos(*2*3)-
/2(*1,*2,*3)=x i-81(*2+o.l)2+sin*3+1.06 ,
and
I O TT-3MXUX 2,*3)=eX'X2+20*3+3
TheJacobian matrix J(x)forthissystem is
3 *3sin*2*3*2sin*2*3
—162(*2-F0.1) cos*3-x,*27(*, *2»*3)= 2*.
20—x2e~x'X2-x\e
Forp1)1=(0.1,0.1,-0.1)'wehave
F(p<0))=(-0.199995 ,-2.269833417 ,8.462025346 )'
and
9.999833334 x10“49.999833334 x10“41-32.43
J(p(0))= 0.2 0.9950041653
-0.09900498337 -0.09900498337 20
Solving thelinear system 7(p(0))y(0)=-F(p(0))gives
0.4998696728
0.01946684853-0.52152047180.3998696728-0.08053315147-0.4215204718(0)_and p(,)=p(0)+y(0)=y
Copyright 2012 Cerifapc Learn in*.AIRights Reversed May rotbecopied.scanned.ocdedicated.»whole oempan.Doc 10electronic rights.some third pony content may besuppreved rrom theeBook andtor cCh<xcn»l.Editorial review h*>
deemed Cutanysuppressed content does notmaterial yalTcct theoverall learning experience .Cenitape l.camopreserves theright 10remove additional conceal atanytime i isubseqjrni rights restrictions require It418 C H A P T E R 10 Systems ofNonlinear Equations
Continuing fork=2,3,...,wehave
(*)i (*-!)“  (*-!)'Pi P1^1
(A) (A-l) (*-l)+ P1 P i y i
(A) (A-1) (A-l)
-P3- LP3 L>3
where
-(A-n-
(A—1) (A—1) (A—1) (A-l)(A—1)\
*P3)*(A-l)i J{P l ’P i ’P i y i
(A-l)^3
Atthek\hstep ,thelinear system J(p i k]))y{k!)=—F(p(*_,))must besolved ,where
pt')Pr')pry
cosp<*-'> -162(pf*1)+0.l)
,,(*-l)„(*-l)e~p\p23
(A-l)J(ptt-w2p! )=
(A-l)_(*-!)r P t X)e-p'
-y(k-i y
y?-l).
-(A-l)(A-l)20 -Pi
y(A-D_
and
3p“-°
F(p(*-'>)=(p{*_
l>)2-8l(p2*-1>+0.1)2+sinpf_l>+1.06
n(A-l)(A-l)^„e~P\ P2+20/?3
Theresults using thisiterative procedure areshown inTable 10.1 .-cospfr-V'M 1
(A-l) IO.T-3
Table 10.1*(A) (A) (A)llp(A)-p'A-Dloc P i P ip>
0 0.1000000000
0.4998696728
0.5000142403
0.5000000113
0.5000000000
0.50000000000.1000000000
0.0194668485
0.0015885914
0.0000124448
8.516 x10-'°-1.375 x10"n-0.1000000000-0.5215204718-0.5235569638-0.5235984500-0.5235987755-0.52359877560.4215204718
1.788 x10“2
1.576 x10"3
1.244 x105
8.654 xlO"101
2
3
4
5
Theprevious example illustrates thatNewton ’smethod canconverge very rapidly once
anapproximation isobtained thatisnear thetruesolution .However ,itisnotalways easy
todetermine starting values thatwilllead toasolution ,andthemethod iscomputationally
expensive .Inthenext section ,weconsider amethod forovercoming thelatter weakness .
Good starting values canusually befound bythemethod discussed inSection 10.4 .
Copyright 2012 Cengagc Learn in*.AIRights Reversed May rotbecopied ,canned ,ocimplicated ,inwhole orinpar.Doc tocjectronie rlghtv .some third pur.ycontcir .may besupplied rican theeBook and/orcChapccriM .Editorial review h*>
deemed Cutany suppic-edcontent does notmaterial yalTcct theoverall learning experience .('engage [.cammureserves theright 10remove additional conteat atanytime ifsubvcqjem nghtv restrictions require IL419 10.2 Newton 'sMethod forSystems
E X E R C I S E S E T 10.2
Give anexample ofafunction F:R2—R:thatiscontinuous ateach point ofR:except at(1,0).
Give anexample ofafunction F:R3-R3thatiscontinuous ateach point ofR3except at(1,2,3).
UseNewton ’smethod with p0)=0tocompute pforeach ofthefollowing nonlinear systems .1.
2.
3.
14x2-20x,+-*f+8=0,\.*\x\+2xi-5X2+8=0.
sin(47rx,x2)-2x2—Xi=0,
(e2*1—e)+Aex;—2ex\=0.
3x,-cos(x2x3)-
^=0,
Ax]-625xf+2*2-1=0,
IOTT-3a.
b.
(^)
d.x]+*2
*,-x\
*1+*2+*3-3=0.-37=0,-5=0,c.
e-*l*2+20*3+ =0.3
4. UseNewton ’smethod tofindasolution tothefollowing nonlinear systems inthegiven domain .Iterate
until ||p(t)-p(*_
1)|l3o<10-6.
3*?—*2=0,
3*i*J—*3—1=0.
Usep(0)=(1,l)1.b.ln(xf+*2)-sin(*!*2)=In2+lnrr,
ex'~*2+cos(*i*2>=0.
Usep(0)=(2,2)'.a.
C. X]+*f*2—*1*3+6=0,
e*'+e*'-*3=0,
x;—2*1*3=4.
Usep(0)=(—1,—2,1)'.
Thenonlinear system6*!—2cos(*2*3)—1=0,
9*2+y/x]+sin*3+1.06+0.9=0,
60*3+3e_
JI|Jt2+107r—3=0.
Usep(0)=(0,0,0)'.d.
5.
*f-*2+2*2=0,
2*,+xf-6=0.
hasfour solutions .They arenear (—5,-4)',(2,—1)',(0.5,2)',and(—2,3)'.Usethese points as
initial approximations forNewton ’smethod anditerate until||p(4)-pk-,)||x<10'6.Dotheresults
justify using thestated points asinitial approximations ?
Thenonlinear system 6.
2x\—3*2+*3—4=0,
2*i+*2—*3+4=0,
x]+*|+x\-4=0.
hasasolution near (—0.5,—1.5,1.5)'.
a.Usethispoint asaninitial approximation forNewton ’smethod anditerate until llp^—plk_,)|loc<
io-6.
b.Solve thefirst twoequations for X\and*3interms of*2.
c.Substitute theresults of(b)intothethird equation toobtain aquadratic equation in*2.
d.Solve thequadratic equation in(c)bythequadratic formula .
e.Ofthesolutions in(a)and(d),which iscloser totheinitial approximation (-0.5,-1.5,1.5)'?
Copyright 2012 Cc«£»fcLearn in*.AIR.(huReversed Mayr*xbecopied ,canned ,ocdaplicated.»whole oempan.Doctoelectronic rifhu.vonte third pony content may besuppressed rrom theeBook and/orcClupccnM .Editorial roiew h*>
deemed Cutanysuppressed content dees notimxttaly alTect theoverall leamir*experience .Ccfiitapc Learn xipreserves thert|>lttloremose additional conceal atanytimeiisubseqjcot rights restrictions require It.420 C H A P T E R 1 0 Systems ofNonlinear Equations
7. Thenonlinear system
l-COS(*2X3)~-=0,
x?-625*f-\=°.
IOTT-33*,
e~*1*2+20*3+ =03
hasasingular Jacobian matrix atthesolution .Apply Newton ’smethod with p*0)=(1,1—1)'.Note
thatconvergence may beslow ormay notoccur within areasonable number ofiterations .
The nonlinear system 8.
4*1-*2+*3=*1*4,
-*1+3*2-2*3=*2*4,
*1-2*24-3*3=*3*4,
*!+*!+*!=i
hassixsolutions .
a.Show thatif(xj,x2,*3,x4)'isasolution ,then (-*,,-x2,-*3,x4)'isasolution .
b.UseNewton ’smethod three times toapproximate allsolutions .Iterate until  p<)—pA_l)||.<
105.Usetheinitial vectors (1,1,1,1)',(1,0,0,0)',and(1,-1,1,-1)'.
LetAbeannxnmatrix andFbethefunction from R"toR"defined byF(x)=Ax.What isthe
Jacobian matrix ofF?
InExercise 6ofSection 5.7,weconsidered theproblem ofpredicting thepopulation oftwospecies
thatcompete forthesame food supply .Intheproblem ,wemade theassumption thatthepopulations
could bepredicted bysolving thesystem ofequations9.
10.
dx 1(0=x,(r)(4-0.0003*i(r)-0.0004*2(r»dt
and
dx2(0=*2(0(2-0.0002 *,(0-0.0001 *2(r)).dt
Inthisexercise ,wewould like toconsider theproblem ofdetermining equilibrium populations of
thetwospecies .Themathematical criteria thatmust besatisfied inorder forthepopulations tobeat
equilibrium isthat,simultaneously ,
dx.(0=0and^(/)=0.dt dt
This occurs when thefirstspecies isextinct andthesecond species hasapopulation of20,000or
when thesecond species isextinct andthefirstspecies hasapopulation of13,333.Cananequilibrium
occur inanyother situation ?
The amount ofpressure required tosink alarge ,heavy object inasofthomogeneous soilthatlies
above ahard base soilcanbepredicted bytheamount ofpressure required tosink smaller objects
inthesame soil.Specifically ,theamount ofpressure prequired tosinkacircular plate ofradius ra
distance dinthesoftsoil,where thehard base soilliesadistance D>dbelow thesurface ,canbe
approximated byanequation oftheform11.
p=kxek2r+*3r,
where k\,ki,and*3areconstants ,withki>0,depending ondandtheconsistency ofthesoilbut
notontheradius oftheplate.
Copyright 2012 Cengagc Learn in*.AIRights Reserved Mayr*xbecopied.scanned .oeimplicated ,inwhole orinpar.Doctocjectronie rights.some third pur.ycontent may besuppreved rrom theeBook and/orcChapccmi .Editorial review h*>
deemed Cutany MJPPIC-CVJcontent does notmaterialy alTcct theoverall Icamir*experience .Ceagage [.cammu reserves theright*>remove additional conceal atanytime ifvutoeqjeni nghtv restrictions require It421 10.3 Quasi-Newton Methods
a.Find thevalues ofk\,k2,and &3ifweassume thataplate ofradius 1in.requires apressure of
10lb/in.2tosink 1ftinamuddy field ,aplate ofradius 2in.requires apressure of12lb/in.2to
sink1ft,andaplate ofradius 3in.requires apressure of15lb/in.2tosinkthisdistance (assuming
thatthemud ismore than 1ftdeep ).
b.Useyour calculations from (a)topredict theminimal sizeofcircular plate thatwould berequired
tosustain aload of500lbonthisfield with sinkage oflessthan 1ft.
10.3 Quasi -Newton Methods
Asignificant weakness ofNewton ’smethod forsolving systems ofnonlinear equations
istherequirement that,ateach iteration ,aJacobian matrix becomputed andannxn
linear system solved thatinvolves thismatrix .Toillustrate themagnitude ofthisweakness ,
consider theamount ofcomputation associated with oneiteration ofNewton ’smethod .
TheJacobian matrix associated with asystem ofnnonlinear equations written intheform
F(x)=0requires thatthen2partial derivatives ofthencomponent functions ofFbe
determined andevaluated .Inmost situations ,theexact evaluation ofthepartial derivatives
isinconvenient ,andinmany applications itisimpossible .This difficulty cangenerally be
overcome byusing finite-difference approximations tothepartial derivatives .Forexample ,
fj(x+het)-fj(x)BJl(x)^dxk h
where hissmall inabsolute value ande*isthevector whose only nonzero entry isa1in
thek\hcoordinate .
This approximation ,however ,stillrequires that atleast n2scalar functional evalua -
tions beperformed toapproximate theJacobian matrix anddocs notdecrease theamount of
calculation ,ingeneral 0(n3),required forsolving thelinear system involving thisapprox -
imate Jacobian .The total computational effort forjustoneiteration ofNewton ’smethod
is,consequently ,atleastr+nscalar functional evaluations (n2fortheevaluation ofthe
Jacobian matrix andnfortheevaluation ofF)together with0(n3)arithmetic operations to
solve thelinear system .This amount ofcomputational effort canbeprohibitive except for
relatively small values ofnandeasily -evaluated scalar functions .
Inthissection ,weconsider ageneralization oftheSecant method tosystems ofnon-
linear equations ;inparticular ,atechnique known asBroyden ’smethod (see[Broy ]).The
method requires only nscalar functional evaluations periteration andalso reduces the
number ofarithmetic calculations to0(n2).Itbelongs toaclass ofmethods known as
least-change secant updates thatproduce algorithms called quasi -Newton .These methods
replace theJacobian matrix inNewton ’smethod with anapproximation matrix thatisup-
dated ateach iteration .Thedisadvantage tothemethod isthatthequadratic convergence
ofNewton ’smethod islost.Itisreplaced bysuperlinear convergence ,which implies that
llp(,>1)-pll
i^*oo||p('>—pH
where pdenotes thesolution toF(x)=0,andp1r>andp+11areconsecutive approximations
top.Inmost applications ,thereduction tosuperlinear convergence isamore thanacceptable
trade -offforthedecrease intheamount ofcomputation .
Anadditional disadvantage ofquasi -Newton methods isthat,unlike Newton ’smethod ,
theyarenotself-correcting .Newton ’smethod ,forexample ,willgenerally correct forround -
offerror withsuccessive iterations ,butunless special safeguards areincorporated ,Broyden ’s
method willnot.lim
Copyright 2012 Cengagc Learn in*.AIR.phtsReserved Mayr*xbecopied ,canned ,oeduplicated.»whole o tmpan.Doctoelectronic rights.some third pony content may besuppressed ftem theeBook and/orcClupccris !.Editorial review h*>
deemed Cut artysuppressed content decs notmaterial'.yafTcct theoverall learnire experience .Cenitape Learning reserves theright Mremove additional conceal atanytime i!subseqjrnt right*restrictions require It.4 2 2 C H A P T E R 1 0 »Systems ofNonlinear Equations
Todescribe Broyden ’smethod ,suppose thataninitial approximation p(0)isgiven to
thesolution pofF(x)=0.Wecalculate thenext approximation p(,)inthesame manner as
Newton ’smethod ,or,ifitisinconvenient todetermine J(p<0))exactly ,wecanusedifference
equations toapproximate thepartial derivatives .Tocompute pl2),however ,wedepart from
Newton ’smethod andexamine theSecant method forasingle nonlinear equation .The
Secant method differs from Newton ’smethod because ituses
f(pi)-fipo )/'(Pi)*Pi-Po
instead of/'(pi).Fornonlinear systems ,p"—p(0)isavector ,and thecorresponding
quotient isundefined .However ,themethod proceeds similarly inthatwereplace thematrix
J(p1!))inNewton ’smethod byamatrix A\with theproperty that
A,(pf>-p<°>)=F(p<‘>)-F(p<°>).
Any nonzero vector inRncanbewritten asthesum ofamultiple ofp1)—p(0)anda
multiple ofavector orthogonal top(l)—p(0).So,touniquely define thematrix Aj,weneed
tospecify how itactsonvectors orthogonal top1"—p(0).
Noinformation isavailable about thechange inFinadirection orthogonal top11}—p(0),
sowesimply require thatnochange occurs when defining A\.That is,
A\Z=7(p(0))zwhenever (p(1)—p(0))'z=0.
Thus anyvector orthogonal top(I)-p(0)isunaffected bytheupdate from 7(p(0)),which
wasused tocompute p",toA],which isused inthedetermination ofp(2).
These conditions uniquely define A\(seeExercise 8)as
[F(P<»)-F(p<°>)-y(p(0))(p">-p(0)>]
At=/(p<0))+ (p<»_p(0))'. (10.1)
IIP(I)—P<0)lll
Itisthismatrix thatisused inplace ofJ(p,l))todetermine p(2):
p(2)=p(i)_A-»F(p(,)).
Once p(2)hasbeen determined ,themethod canberepeated todetermine p(3),with A\
used inplace ofAo=./(p(0))andwith p(2)andp"inplace ofp"andp(0),respectively .
Tosimplify thenotation weintroduce thevariables
and y,=F(p(,))-F(pu~l)).
Then ,once p"hasbeen determined ,p'+l)canbecomputed bys,=p<'>-p"-1*
[F(ptf))~F(pg-»)]-Aj-i(p(l^-ptt-”)_p(l_
1)y A,=A,_j+iip(.)-p(‘-»ni
—A,iS/ _
A ,y<—A,_
iH s.
Us,ill
and
p0+»=p(O_
Ar,F(p(.)).
Ifthemethod isperformed asoutlined ,thenumber ofscalar functional evaluations is
reduced fromn2+nton(those required forevaluating F(p(,))),butthemethod stillrequires
0(n3)calculations tosolve theassociated nxnlinear system
AjSi+i=-F(p“’).
Copyright 2012 Cc«£»fcLcarnin*.AIRighb Reversed May notbecopied .canned ,ocduplicated.»whole oempar.Doc 10electronic itfhu .some third puny content may besuppreved rrom theeBook and/orcCh<xcn»l.Editorial review h*>
deemed Cut ait)suppicwcd conteendoev notimxtlily alTcct theiAcra .lteamireexperience .Ccngjgc Learn rornct thenjht Mremove additional conceal atanytime i!vubveqjcnt nythav rcvtrictionc require It.423 10.3 Quasi -Newton Methods
Employing themethod inthis form would notbejustified because ofthereduction to
superlinear convergence from thequadratic convergence ofNewton ’smethod .However ,a
significant improvement canbeincorporated byemploying amatrix -inversion formula .
Sherman -Morrison Formula
Sherman -Morrison Formula
IfAisanonsingular matrix andxandyarevectors with y'A*x^—1,then A+xy'
isnonsingular and
-lA~’xy'A
lTy'A^x' (A+xy')-1=A-1
This formula permits A"1tobecomputed directly from A-leliminating theneed
foramatrix inversion with each iteration .This computation involves only matrix -vector
multiplication ateach step andtherefore requires only0(n2)arithmetic calculations .
Byletting A=A,_i,x=(y
*-A,_iSl)/||sl||§,andy=s,,theSherman -Morrison
formula implies that»-i»
-l( )y.-Aj.js,A"1si A,_i+ ills,II;
) (y,--Ai_,s, -1 -1S'A^i-i /-lMl -1=Ai-1“
( )y i-A^S il+s'A.Ji
IISill2
(A-^y,-s,)s'A-1
1-1=A(-J,-||s,Hi-t-s'A.Jjy,-||s,|||
(s,-Viy.)»iA-1
1-1 -1Theprogram BROYM 102
implements Broydcn ’s
method .=Ai-lsJA-^y,
Thecalculation ofA,-isbypassed ,asisthenecessity ofsolving thelinear system .
Example 1Use Broyden ’smethod withp(0)=(0.1,0.1,-0.1)'toapproximate thesolution tothe
nonlinear system
13*!-COS(*2*3)“-=0,
x2-81(*2+0.1)2+sinx 3+1.06=0,
10TT-3e~x'X2+20X3+ =0.3
Solution This system wassolved byNewton ’smethod inExample 1ofSection 10.2 .The
Jacobian matrix forthissystem is
3 *3smX 2^3
162(JC2+0.1)-x\X2X2sm X2X3
COS*3 2x, J(x1,X2,X3)=
20 -or1*2 -x2e -xxe
Copyright 2012 Cenfajc Lcarnin*.AIRighb Reversed May notbecopied ,canned ,ordaplicatod .»whole oempar.Doctoelectronic ilfhu.xvtic third pur.ycontent may besuppreved Tiom theeBook and/orcCh<xcn»l.Editorial roiew h*>
deemed Cutanyvuppicvvcd content doev nottmxtlaly alTect theoverall Icamir .itexperience .C'cnitasc[.camon reserve*therljtlu toremote additional concert atanytime i ivubveqjcnt rights rotrictionv require It424 C H A P T E R 10 Systems ofNonlinear Equations
Letp(0)=(0.1,0.1,—0.1)'and
F(*i.*2.*3)=(/i(-*1.*2.*3)1/2(^1.*2.-*3).M X U X 2,x3))',
where
1f](x1,JC2,X3)=3*i-cos(x2*3)-2»
/2(^1»^2.^3)=x]-81(^2+0.1)2+sinx 3+1.06 ,
and
10TT-3
*2.*3)=e~x'X2+20*3+3
Forp0)=(0.1,0.1,-0.1)'wehave
"—1.199950
F(p(0))=-2.269833
8.462025
This implies that
A0=y(p(0))
-9.999833 x10"4‘
0.99500429.999833 x10"4
-32.4-9.900498 x10"23
0.2-9.900498 x10"220
Forthisfirst iteration ,weneed tofind theinverse of(./(p(0))).However ,forsubsequent
iterations ,matrix inversion isnotnecessary .Wehave
At'=j(p?\p?\pfr'
0.3333332
=2.108607 xlO"3
1.660520 xlO"31.615701 xlO"5'
1.535836 xlO’3
5.000768 x10~21.023852 x10"5
-3.086883 x10"2
-1.527577 xlO”4
So
0.4998697
1.946685 xlO'2,-0.5215205p(l)_p(0)_
^-^(p^0))=
-3.394465 x10~4’
-0.3443879
3.188238 x10~2F(p(,))=
1.199611'
1.925445 ,-8.430143y,=F(p(1))-F(p(0))=
0.3998697-8.053315 xlO"2,-0.4215204s,=
Copyright 2012 Ce«£»fcLcirni #*.AIRighb Reversed May n«becopied ,canned ,ordaplicatod .»whole oemport.Doctoelectronic ilfhu .xxtic third pur.ycontent may besuppteved riom theeBook and/orcCh<xcn»l.Editorial roiew h*>
deemed Cutanyvuppicvvcd etnteni dec>notimxttaly alTect theoverall leamir*experience .C'cnitasc[.camonrexrvcv thert|>ht10remote additional conteatatanytime iivubveqjcnt ngh*vroirictionv require It425 10.3 Quasi-Newton Methods
s'Ao'yi=0.3424604 ,
V=V+1[(Sl-Vy.K>V]
1.11050 x10-5
-3.094849 x10“2
-1.650709 x10-40.3424604
0.3333781-2.021270 x10"3
1.022214 x10-38.967344 x10~6‘
2.196906 x10“3,
5.010986 x10-2
and
0.4999863
8.737833 x10"3
-0.5231746(2)=p(i>-AriF(P(i>)= p
Additional iterations arelisted inTable 10.2.The5thiteration ofBroyden ’smethod is
slightly lessaccurate than wasthe4thiteration ofNewton ’smethod given intheexample
attheendofthepreceding section .
Table 10.2k(*) (*>(A) ||p(A)_
p(*-l)||2 P1 Pi Pi
0 0.1000000
0.4998697
0.4999864
0.5000066
0.5000003
0.50000000.1000000
1.946685 x102
8.737839 x10"3
8.672736 x10
3.952827 x105
1.934342 x10-0.1000000-0.5215205
-0.5231746
-0.5235723-0.5235977
-0.5235988-l1 5.93 x10
1.0856 x10"2
7.8806 x10~3
8.2817 x104
3.9351 x10"52
43
4-75
E X E R C I S E S E T 10.3
UseBroyden ’smethod with plD)=0tocompute pl?)foreach ofthefollowing nonlinear systems . 1.
14xf-20x[-I--x\+8=
^*1*24*2xt—5X24-8=0.
sin(4;rxix 2)—2x2—X\=0,0, a.
b.
-e)4-4ex\—2ex\=0.i
13*i-cos(x2*3)--=°.
4*2_625x24-2*,-1=0,c.
1e~x'x*+20*34--(IOTT-3)=0.
xf4-*2
*,-*|
*,4-*24-*3-3=0.
UseBroyden ’smethod toapproximate solutions tothenonlinear systems inExercise 1using the
following initial approximations p,u>until||p‘1-pa-I)||00<10~6.
(1»1»l)f-3 7=0,-5=0,d.
2.
a.(0,0)' d.(2,i,-i y b.(0,0)' c.
Copyright 2012 Cengagc Learning .AIRights Reversed May notbecopied ,canned ,orduplicated .inwhole orinpar.Doctoelectronic rights.xxtic third pur.ycontent may bevuppreved rrom theeBook andtor eChaptcnnl .Editorial roiew h*>
deemed Cutanysuppressed content does nottnaxrUXy alTcct theoverall learning experience .Ccttgagc [.cammerorntt theright 10remose additional conteatatanytime iisubseqjcnt rights restrictions require It426 C H A P T E R 10 Systems ofNonlinear Equations
Use Broyden ’smethod tofindasolution tothefollowing nonlinear systems ,iterating until ||p(k)-
p^loo<lO"6.3.
3x\-x;=0
3x\x;—x*—1=0
Usep(0)=(l,l)'.
ln(xf4-x|)-sin(jcijr2)=In24-Inn
4.COS(JC,JC2)=0
Usep(0)=(2,2)'.
x]+x\x2-X{X y4-6=0
e*1+e*i-X)=0
x\—2x\X$=4
Usep(0)=(-1,-2,1)'.
6*12COS(*2*3)-1=0
9*24-y/xJ4-sinx 34-1.06 4-0.9=0
60x34-3e~x'x*4-IOTT-3=0
Usep(0)=(0.0.0)'.
Thenonlinear systema.
b.
c.
d.
4.
1-cos(x2x3)-2
-625x|-i=0.
+20*3+*(10JT3)=0
hasasingular Jacobian matrix atthesolution .Apply Broyden ’smethod withp(0)=(1,1-1)'.Note
thatconvergence may beslow ormay notoccur within areasonable number ofiterations .
Thenonlinear system3*i =0.
x?1
e~xxx‘
5.
4xy-x2+x$=xxxA %-*14-3X2~2X3=x2xA,
xx-2x2+3X3=X3X4,
x]4*x\4-x\=1
hassixsolutions ,and,asshown inExercise 8ofSection 10.2,(—xu-x2,-x3,x4)isasolution
whenever (xltx2,x3,x4)isasolution .UseBroyden ’smethod toapproximate these solutions .Iterate
until||p(t)-p^-»||<J0<10'5.Usetheinitial vectors (1,1,1,1)',(1,0,0,0)',and(1,-1,1,-1)'.
Show thatif0^yGR"andzGRn,thenz= 4-z2,where 6.
t± -jllylllz,=
isparallel toyandz2=z-Z|isorthogonal toy.
Show thatifzisorthogonal top(,)—p<0),then forA\defined inEq.(10.1)wehave A\=y(p<0)). 7.
8. Let
[F(p(1)>-F(p<°>>-y(p<0,)(p(1)-p(0))](P(1)-p(0)y
A,=y(p,0>)+iipin_p<o>n|
a.Show that A,(p<l)—p(0))=F(p(,))—F(p(0)).
b.Show thatAlz=7(p(0>)zwhenever (ph-p(0>)'z=0.
Copyright 2012 Cenfa*cLcarni #*.AIRighb Rcicfved .May ncabecopied .icanacd .orAliened.»whole oempnn .Doc 10electronic itfhu .*wtcthird pur.yCOMCK may besuppreved riom theeBook amtar cCh<xcn»l.Editorial toiew h*>
deemed CutanyMpprcucd cement dee>notmaterial yalTccr theoverall Icamir*experience .Ccnitasc [.camonroerver theright lorerrxyve additional conteat*anytime ifwtoeqjcoi nght »rotrietionc require IL427 10.4 TheSteepest Descent Method
Itcanbeshown thatifA_
lexists andx,yR",then (A+xy')~lexists ifandonly ify'A~1x^—l.Use
thisresult toverify theSherman -Morrison formula :IfA1exists andy'A1x^-1,then (A+xy')
exists ,and9.-l
A'lxy'A
1+y,A-1x‘-l
(A+xy')1=A1
10.4 TheSteepest Descent Method
Theadvantage oftheNewton andquasi-Newton methods forsolving systems ofnonlinear
equations istheir speed ofconvergence once asufficiently accurate approximation isknown .
Aweakness ofthese methods isthatanaccurate initial approximation tothesolution is
needed toensure convergence .Themethod ofSteepest Descent willgenerally converge
only linearly tothesolution ,butitisglobal innature ,thatis,nearly anystarting value will
give convergence .Asaconsequence ,itisoften used tofindsufficiently accurate starting
approximations fortheNewton -based techniques .
Themethod ofSteepest Descent determines alocal minimum foramultivariable func-
tionoftheform g:R"-R.The method isvaluable quite apart from providing starting
values forsolving nonlinear systems ,butwewillconsider only thisapplication .
Theconnection between theminimization ofafunction from R"toRandthesolution
ofasystem ofnonlinear equations isduetothefactthatasystem oftheform
/l(*l.*2 *<)=0,
/2(*l.*2 X„)=0,Thename fortheSteepest
Descent method follows from the
three-dimensional application of
pointing inthesteepest
downward direction .
f n(X\,X2 X n)=0,
hasasolution atx=(JCJ,*2,   .x„yprecisely when thefunction gfrom R"toRdefined
by
Xn)= .*n)]2g(x1,*2,.. »
1-1
hastheminimal value zero.
Themethod ofSteepest Descent forfinding alocal minimum foranarbitrary function
gfrom R"intoRcanbeintuitively described asfollows :
 Evaluate gataninitial approximation p())=(pj0),p f\...,p<0))f.
 Determine adirection from p(0)thatresults inadecrease inthevalue ofg.
 Move anappropriate amount inthisdirection andcallthenewvalue p[).
 Repeat thesteps with p(0)replaced byp11}.
TheGradient ofaFunction
Before describing howtochoose thecorrect direction andtheappropriate distance tomove
inthisdirection ,weneed toreview some results from calculus .TheExtreme Value Theorem
implies thatadifferentiable single -variable function canhave arelative minimum within
Copyright 2012 Cengagc Learn in*.AIRight*Reversed Mayr*xbecopied.v.-aitned.o*implicated ,inwhole orinpar.Doctocjectronie rifhu.*wcthird pur.ycontent may besupplied rican theeBook and/orcChaptcnM .Editorial roiew h*>
deemed CutanyMpprccscd content dce>notnuetlaXy afTcct theoverall learnire experience .Cette jpeLearn xiercsenn theright Mremove additional conceal atanytime i!vutoeqjrni right*rotrictiots require It.428 C H A P T E R 10 Systems ofNonlinear Equations
The rootofgradient comes from theinterval only when thederivative iszero.Toextend thisresult tomultivariable functions ,
theLatin word gradi,meaning
“towalk ”.Inthissense ,the
gradient ofasurface istherateat
which it“walks uphill ”.weneed thefollowing definition .
Ifg:Rn-¥R,wedefine thegradient ofgatx=(*i,x2,..., Vg(x),by
v*(x)=(S(x)’
The gradient foramultivariable function isanalogous tothederivative ofasingle
variable function inthesense thatadifferentiable multivariable function canhave arelative
minimum atxonly when thegradient atxisthezero vector.
Thegradient hasanother important property connected with theminimization ofmul-
tivariable functions .Suppose v=(uj,V2,...,vnYisavector inR”with ||v||2=1.The
directional derivative ofgatxinthedirection ofvisdefined byS' d g
*“’dx
Dvg (x)=limi[g(x+h\)-g(x)]=v*Vg(x)=^^x)*d g
i=l
Thedirectional derivative ofgatxinthedirection ofvmeasures thechange inthevalue of
thefunction grelative tothechange inthevariable inthedirection ofv.
Astandard result from thecalculus ofmultivariable functions states thatthedirection
thatproduces themaximum increase forthedirectional derivative occurs when vischosen
inthedirection ofVg(x),provided thatVg(x)^0.Sothemaximum decrease will bein
thedirection of—Vg(x).
 Thedirection ofgreatest decrease inthevalue ofgatxisthedirection given by-Vg(x).
SecFigure 10.2foranillustration when gisafunction oftwovariables .
Figure 10.2
z
Theobjective istoreduce g(x)toitsminimal value ofzero,sogiven theinitial approx -
imation p(0),wechoose
p'D_
p(0)_
QfVgCp '0*) (10.2)
forsome constant a>0.
Copyright 2012 Cc«£»fcLearn in*.AIR.(huReversed Mayr*xbecopied ,canned ,orduplicated.»whole ormpan.Doctoelectronic rifhu.vonte third pony content may besuppressed ftem theeBook and/orcCh<xcn»l.Editorial review h*>
deemed Cut artysuppressed content dees notimtetlaly affect theoverall teamireexperience .Cenitapc Learn xiprcsenn thenjht Mremove additional conceal atanytime i!suhvenjcni nphts restrictions require it429 10.4 TheSteepest Descent Method
Theproblem now reduces tochoosing orsothatg(p!1})willbesignificantly lessthan
g(p(0)).Todetermine anappropriate choice forthevalue or,weconsider thesingle -variable
function
*(«)=S(P<0)-aVg (p(0»)).
Thevalue ofathatminimizes histhevalue needed forp=p(0)—aVg(p(0)).
Finding aminimal value forhdirectly would require differentiating handthen solving
aroot-finding problem todetermine thecritical points ofh.This procedure isgenerally too
costly.Instead ,wechoose three numbers a\<0*2<«3that,wehope ,areclose towhere
theminimum value ofh(a)occurs .Then weconstruct thequadratic polynomial P(x)that
interpolates hatoq,«2»and 0*3.Wedefine ain[ct\,«3]sothatP(a)isaminimum in[a\,«3]
anduseP(a)toapproximate theminimal value ofh(a).Then aisused todetermine the
newiterate forapproximating theminimal value ofg:
(0)-aVg (p(0>).(1)P'=p
Since g(p,0))isavailable ,wefirstchoose a\=0tominimize thecomputation .Next a
number 0*3isfound with h{a3)<h(a\).(Since a\does notminimize h,such anumber «3
does exist.)Finally ,«2ischosen tobe0*3/2.
Theminimum value aofP(x)on[aj,0*3]occurs either attheonly critical point ofP
orattheright endpoint 0*3because ,byassumption ,P(ot))=h(a3)<h(a\)=P(ct\).The
critical point iseasily determined because P(x)isaquadratic polynomial .
Program STPDC 103applies themethod ofSteepest Descent toapproximate themin-
imal value ofg(x).Tobegin each iteration ,thevalue 0isassigned toot],andthevalue 1is
assigned to0*3.If/1(0*3)>/1(0*1),then successive divisions of0*3by2areperformed and
thevalue of**3isreassigned until /1(0*3)</*(<*i)-
Toemploy themethod toapproximate thesolution tothesystemTheprogram STPDC 103
implements theSteepest
Descent method .
/i(xi,x2,...,X„)=0,
/2(^1»-*2»    xn)=
/n(*l,*2,...,*n)=0,
wesimply replace thefunction gwithYH=\J7-
Example 1Use theSteepest Descent method with pl0)=(0,0,0)'tofindareasonable starting ap-
proximation tothesolution ofthenonlinear system
:/l(Xj,X2,*3)=3*!-COS(x2X3)”2=0’
/2(*1»*2,*3)=x\-81(X2+0.1)2-fsin*3+1.06=0,
10TT-3M*1,*2,*3)=eX l X2+20X3+ =0.3
Copyright 2012 Cengagc Learn in*.AIRighto Reversed May rotbecopied.wanned .o*implicated ,inwhole orinpar.Doctocjevtronie rightv.some third pur.yCOMCK may besupplied ftem theeBook and/orcChapccriM .Editorial review h*>
deemed Cutanysupprewed content doev notimtetlaly afTcct theoverall Ieamir .itexperience Ccnit jpeLearning roervev theright Mremove additional conceal atanytime i!vuhvajjcM nghtv rotrictions require It.430 C H A P T E R 10 Systems ofNonlinear Equations
Solution Letg (xi,x2,x3)=[/i(x,,x2,x3)]2+[/2U1,x2,x3)]2+[/3U1,*2»X3)]2.Then
=(2/,(X)^(X)+2/2(X)^(X)+2/3(X)^(X), V«(JT1,^2,*3)=Vg(x)3A:, 3AC,
3/, 3/2 3/32/,(x) (x)+2/2(x) (x)+2/3(x) (X).3*2 3X2 dx2
(x)j3/i 3/2 3/32/1(X)—(x)+2/2(x) (x)+2/3(X)9X3 9x3 9x3
=2J(x)'F(x).
Forp0)=(0,0,0)',wehave
8(P(0))=/.(0,0,0)2+/2(0t0,0)2+/3(0,0,0)2
2
+(-81(0.01)+1.06)2+(^=111.975 ,
and
Zo=l|Vg(p<0>)||2=l|2J(0)'F(0)||2=419.554 .
Let
1z=-Vg(p(0>)=(-0.0214514 ,—0.0193062 ,0.999583 )'.zo
With ai=0,wehave gi=g(pl0)-a\Z)=g(p<0))=111.975 .Wearbitrarily leta3=1
sothat
(0)-a3z)=93.5649 . S3=s(p
Because <g\,weaccept <*3andseta2=a3/2=0.5.Evaluating gatp(0)—a2zgives
82=«(P<0)-a2z)=2.53557 .
Wenow find thequadratic polynomial that interpolates thedata (0,111.975 ),
(1,93.5649 ),and (0.5,2.53557 ).Itismost convenient touseNewton ’sforward divided -
difference interpolating polynomial forthispurpose ,which hastheform
P{(*)=Si+h\ct+h-sct{a-a2).
This interpolates
S(P(0)-aVg (p(0)))=g(plU)-az)
atafi=0,(*2=0.5,anda3=1asfollows :
«i=0, Si=111.975 ,
8 2-8 1«2=0.5,g2=2.53557 ,/z,= =-218.878 ,«2«1
h2-h\ 83-82=93.5649 ,h2= =182.059 , h3= =400.937 . «3=1,«3-«2 «3-«i
This gives
P(a)=111.975-218.878 a+400.937 a(a-0.5)=400.937 a2-419.346 a+111.975
Copyright 2012 Cengagc Learning .AIRtghb Reversed May rotbecopied ,canned ,ordaplicated.»whole ormpan.Doctoelectronic right*.vonte third pony content may bevupprcvscd riom theeBook and/orcCh<xcn»l.Editorial roiew h*>
deemed Cutanyvuppicwed content doev notimtctlaly alTect theoverall learning experience .Ceng age[.cammgroentt theright 10remote additional conceal atanytime ifsubvoyjem nght >rotrictionv requite It431 10.4 TheSteepest Descent Method
so
P\a)=801.874 a-419.346
and P(a)=0when a=oro=0.522959 .Since
g(p<0)-a0z)=2.32762
issmaller than g]and#3,weset
p<'>=p<°>-a0z=p<0)-0.522959 Z=(0.0112182 ,0.0100964 ,-0.522741 )I
and
g(p(,))=2.32762 .
Table 10.3contains theremainder oftheresults .Atruesolution isp=(0.5,0,-0.5235988 )',
sop'2)would likely beadequate asaninitial approximation forNewton ’smethod or
Broyden ’smethod .One ofthese quicker converging techniques would beappropriate
atthisstage because 70iterations oftheSteepest Descent method arerequired tofind
llp(*>-Plloo <0.01.
Table 10.3k_(*)Pi P?>_
<*>P)
2 0.137860
0.266959
0.272734
0.308689
0.314308
0.324267-0.205453
0.00551102-0.00811751-0.0204026-0.0147046-0.00852549-0.522059-0.558494-0.522006-0.533112-0.520923-0.5284311.27406
1.06813
0.468309
0.381087
0.318837
0.2870243
4
5
6
7
EXERCISE SET 10.4
l. Use themethod ofSteepest Descent toapproximate asolution ofthefollowing nonlinear systems ,
iterating until||plA)—plt_,)||oc<0.05.
1Ax]-20x,+-xf+8=0
5x2+8=0a.
1-x\x$+2xi-
3*?-4
3*,xf-*,3-1=0
c.ln(xf+x\)—sin(xiX 2>=In2+ln;r
e*i~*2+cos(xi*2)=0
sin(47rxijc 2)—2JC2 x\=0
(e2*1-e)4-Aex\-2ex\=0
Usetheresults inExercise 1andNewton ’smethod toapproximate thesolutions ofthenonlinear
systems inExercise 1,iterating until||p(A)-p(i_
l>||oc<10~6.b. =0
d.
(TT)
2.
Copyright 2012 Cengagc Learning .AIRights Reversed May notbecopied ,canned ,orduplicated .inwhole orinpar.Doctoelectronic rights.xvtic third pur.ycontent may bevuppreved riom theeBook amtar cCh<xcn»l.Editorial roiew h*>
deemed Cutanysuppressed content does nottnaxrUXy alTcct theoverall learning experience .Collage [.cammereserve*theright*>rerrxyve additional conteatatanytime iisubseqjcnt right*restrictions require It432 CHAPTER 10 Systems ofNonlinear Equations
3. Use themethod ofSteepest Descent toapproximate asolution ofthefollowing nonlinear systems ,
iterating until \\p(k)-p(*_1)||oc<005.
a.15*i+*2“4*3=13
*f+10*2_*3=11
x\-25*3=—22
C.*^-fx]x2—*1*3+6=0
exi+e**-x3=0
x\—2*1*3=410*i—2*|+*2—2*3—5=0
8*|+4*f-9=0
8*2*34"4=0b.
*i4-cos(*i*2*3)-1=0
(1-*,),/4+*2+0.05*3-0.15 JC3-1=0
—x\—0.1*1+0.01*2+*3—1=0
Use theresults ofExercise 3andNewton ’smethod toapproximate thesolutions ofthenonlinear
systems inExercise 3,iterating until||p|A>—p'*“,)||00<106.
Use themethod ofSteepest Descent toapproximate minima forthefollowing functions ,iterating
until flp(4)-pt*~,)||00<0.005 .
a.g(xt,x2)=cos(x,4-*2)4-sin*,4-cos*2
b.g(*i,*2)=100(*f-*2)24-(1-*i)2
c.g(*i,*2,*3)=*2+2x\4-*2-2*,*2+2*i-2.5*2-*34-2
d.g(*j,*2,*3)=*44~2*44"3*44"1.01
a.Show thatthequadratic polynomial thatinterpolates thefunction
h(a)=s(p,0)-aVg (p(0>»d.
4.
5.
6.
ator=0,a2,anda3is
P(a)=g(p(0))4-h\a4-/i3or(a-or2)
where
g(p<0)-a2z)-g(p0))ha2
g(p<0>—a3z)—g(p<0)—ar2z) h2-h i,and A3= h2=a3-a2
b.Show thattheonly critical point ofPoccurs atoro=0.5(or2—/11//13).«3
— 10.5 Homotopy andContinuation Methods
Homotopy ,orcontinuation ,methods fornonlinear systems embed theproblem tobesolved
within acollection ofproblems .Specifically ,tosolve aproblem oftheform
F(x)=0,
which hastheunknown solution p,weconsider afamily ofproblems described using a
parameter kthatassumes values in[0,1].Aproblem with aknown solution x(0)corresponds
tok=0,andtheproblem with theunknown solution x(l)=pcorresponds tok=1.
Suppose x(0)isaninitial approximation tothesolution pofF(x)=0.Define
G:[0,1]xR" R"
by
G(k,x)=*F(x)4-(1-k)[F(x)-F(x(0))]=F(x)4-(k-l)F(x(0)).
Copyright 2012 Cengagc Learn in*.AIRights Reversed Mayr*xbecopied.scanned .ocimplicated ,inwhole orinpar.Doctocjectronie rights.some third pur.yCOMCK may besupplied rican theeBook and/orcChapccriM .Editorial review h*>
deemed Cutanysuppressed content does nottnaxrUXy alTcct theoverall learning experience .('engage [.camonreserves theright 10remove additional eonteatatanytime ifsubsequent nghts restrictions require It