### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# INTRODUCTION TO NUMERICAL ANALYSIS MTH 351

OSU

GPA 3.79

### View Full Document

## 9

## 0

## Popular in Course

## Popular in Mathematics (M)

This 10 page Class Notes was uploaded by Mrs. Dedric Little on Monday October 19, 2015. The Class Notes belongs to MTH 351 at Oregon State University taught by N. Gibson in Fall. Since its upload, it has received 9 views. For similar materials see /class/224439/mth-351-oregon-state-university in Mathematics (M) at Oregon State University.

## Popular in Mathematics (M)

## Reviews for INTRODUCTION TO NUMERICAL ANALYSIS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/19/15

BIT 17 1977 321428 A SECANT METHOD FOR MULTIPLE ROOTS RICHARD F KING Abstract A superlinear procedure for finding a multiple root is presented In it the secant method is applied to the given function divided by a divided difference whose increment shrinks toward zero as the root is approached Two function evaluations per step are required but no derivatives need be calculated CR Category 515 Key words and phrases nonlinear equation root finding multiple root secant method Steffensen procedure order of convergence ef ciency stability 1 Introduction We seek a method of secant type for nding a real multiple root or of the nonlinear equation f x0 But direct application of the secant method to xn2 xn1xnxn1 fiEfxi9 yields a procedure whose convergence for a root of multiplicity m gt 1 apparently is linear at best see Espelid 3 Stewart 5 and Woodhouse 7 That is for given initial values x0 and x1 the order of convergence p is l in 8 lt2 312 for errors sixioa Stewart 5 has camputed Km for various mgtl as the posi tive root of K K 1 1 0 Since it is well known that the function Fff has a simple root at a see Traub 1 p 235 for example we can avoid the dif culty of slow linear convergence by applying 1 to F instead of to f Using F however requires that a derivative as well as a function value be calculated each step moreover f is frequently more complicated than f The function F may also be used in Newton s method 12 x J0 1 F2 f6 1 g o 2 2 O 3 x1 x0 Received March 2 1977 Revised July 27 1977 39Wor39k supported by the US Energy Research and Development Administration 322 RICHARD F KING where here and henceforth we suppress n in the subscripts Since F has a simple root at or the process converges quadratically 1 2 whereas f itself in Newton s method yields linear convergence with Km m 1m see Rall 2 The price of gaining quadratic convergence is having to calculate not only f and f but also f Inspired by a procedure due to Steffensen Esser 6 has recently proposed that the derivatives of f in 3 be replaced by divided differences The increment f for these differences is not constant however but shrinks as the root is approached Such a scheme is a natural way of de ning differences with the desired derivative properties Esser s method indeed is quadratic calls for three function evaluations per step and provides the multiplicity m as well as the root at Its efficiency index see Traub l p 263 is 2 1260 2 A method for multiple roots In the same spirit we propose for multiple roots that the secant method be used not with the function F ff but rather with rm m 4 i x fe fegt x re fo39 x f x x Here again f has been replaced by a divided difference of f with increment f It will be instructive to compare G with F to see why both yield superlinear convergence when used as secant method functions First of all we want to find the value of F and its first three derivatives at or Note that if the function f has a root of multiplicity m at at then it may be written as 5 fx xOtmgx gm 0 Furthermore since the secant algOrithm 1 gives x2 as a linear function of x0 and x1 it follows that a translation of f by x o enables us without loss of generality to take 020 Consequently Foc may be expressed in terms of g as xgx mg x xg39 x 6 F 0 x0 ie or is a root of F Differentiating F we see that mglx2glzggn 1 ngrxg 2 i07 m 39 Fo m x0 so that in fact or is a simple root of F Further differentiation shows that 2390 8 W W A SECANT METHOD FOR MULTIPLE ROOTS 323 and that 61 26 w o wmi m It is known for example see Anderson and Bj6rck 4 p 258 that the asymptotic error equation for the secant method with a function F having a simple root at a is II III N 2 10 2 2 2 88081 1 Elt 80818081 where the coef cients may be written in terms of g and its derivatives at or by means of 7 8 and 9 This error equation shows that for any multiplicity m the secant method 1 using F is superlinear The asymptotic convergence rate in fact is 1618 But what about the function G We can expand fx fx in a Taylor series about x to get for small F we 11 G fx fxf xif2xf x 3xf x fx F1FfquotFff t1 tf Evaluating at a0 the results of some very tedious differentiations we conclude that G and its derivatives at any at can be written as mn0 GmFmi m 2 1 p was F aF 2ocf oc 715 n 2f oc 12 G oc Fquot ac3F 2a f oc3F ocF oc f oc F 3af 2oltF 2ocf ocf oc 6ltm1gt amp 155322 i i we gm m2 graiiim2if a 6 g39or H 3 H2 1 m g 05 awf a Wfaf a Furthermore the derivatives of f in 12 are given in terms of g and its derivatives at the root or and for various values of multiplicity m as entries in the following table 324 RICHARD F KING m 1 m 2 m 3 m g 4 f 39 or slit 0 0 0 fquot0 Zg39id 2amp0 0 0 ff 38quot06 6g 630x 0 Thus G has a simple root at at and otherwise exhibits oenavior quite similar to that of F When G is used in the secanl method 01 13 x x x x W t 2 1 0 06041 it produces superlinear convergence The asymptotic error equation for this the proposed method is N 1 G a 1 G oc l G oc 2 14 32 Ea wsosl 8 soslaoal It is well known that for this procedure the order of convergence is p 1 5i2 1618 Since the two function evaluations fx1 and f xl f 361 are required each step it follows that the efficiency index is 1618 1272 Woiniakowski 8 has shown that secant iteration such as that proposed is stable provided only that G be computed by a wellbehaved algorithm For example a polynomial fused in forming G should be evaluated by Homer s rule rather than term by term Furthermore one must remember that in order to calculate a multiple root accurately it is necessary to use multiprecision arithmetic 3 Finding the multiplicity m From 11 and 6 we can see that for small 81 8 061 31 15 G F 1 1 1 mgx181g 351 m Similarly we know that Gz SZm Furthermore 32 81x2 x1 Consequently when nearing the root on we can estimate its multiplicity by computing x x 16 e 2 1 m GrGl Thus in is approximately the reciprocal of the divided difference of G for successive iterates x1 and x2 It may be computed and displayed at each step along with the current iterate Thanks are due to the referee for raising the question of the method s stability A SECANT METHOD FOR MULTIPLE ROOTS 4 Examples H Results from three examples computed in quadruple precision on an IBM 370 are shown in Tables 13 In each case the predicted error 32 as calculated from 14 is seen to be a good approximation to the actual error x oi and the estimated multiplicity m from 16 approaches its actual value No careful convergence criteria were either discussed in the analysis or used in the examples The secant method was also applied to f directly for the examples some 47 69 and 66 steps respectively were required to obtain final accuracy comparable to that of the proposed method REFERENCES I F Traub Iterative Methods for the Solution of Equations PrenticeHall Englewood Cliffs NJ b 23 EC 1964 B Rall Convergence of the Newton process to multiple solutions Numerische Mathematik 9 1966 23 371 O Espelid 0n the behavior of the secant method near a multiple root BIT 11 1972 112 115 Anderson and A Bjorck A new high order method of regula falsi type for computing a root of an equation BIT 13 1975 253 264 W Stewart The convergence of multipoint iterations to multiple zeros SIAM J Numer Anal 11 1974 1105 1120 Esser Eine stets quadratisch konvergente Modi kation des SteffensenVerfahrens Computing 14 1975 367469 Woodhouse A note on the secant method BIT 15 1975 323 327 Woiniakowski Numerical stability for solving nonlinear equations Numerische Mathematik 27 1977 373 390 Table 1 f g m a 81 C 3105 ET 0a GHGX GHQ x 12 tan x4 tan TEX4 2 1 1 1152 1124 12 714 37126 3712 34 8n2 E 41213n3n 3n48n8n18n8nl n x f G x ac a m 0 6 0815241 359569 4 1 7 0551521 205290 3 2 833064 0213742 0934212 166936 232168 11894645 3 19441851 00285348 0285632 0558149 10693915 17132998 4 99312248 0000467920 00344590 00687752 00754945 19483516 5 399836316 267857 7 818460 4 000163684 000166258 19957541 6 999999660143 115501 12 169928 6 339855 6 339961 6 19999062 7 999999999984 25274321 794895 11 158979 10 15897939 10 19999998 93 9ND El RIVHJIH Table 2 f g m 0 g 1 214 3101 G101 GHQ 73910 xx 23 x 3 2 2 1 0 13 19 389 8u2 E 165n5n1 25123n3n13n5n1 n x f G x 05 8 m 0 10 l0 10 10 1 11 8019 803700 9 2 1509423 178210 250516 w 490577 371250 74012233 3 1694836 0481646 124869 305164 135268 14756629 4 1879101 00332062 0422846 120899 273133 22312244 5 19734474 0000369443 00890302 0265526 0388973 28263022 6 199861000 536751 8 000463443 00139000 00152117 29815029 7 199999175536 v 112084 14 00000274822 00000824464 00000829992 29992887 8 199999999806 146785 25 647783 9 l94335 8 194339 8 29999959 SLOOH EHdIJJHW H03 IOHLEIW LNVOEIS V LZE 39V39S39 691709 SIONI I H QNNOQHV HHNEAV SSVO HLHOS 00L6 AHOIVHOHV39I IVNOILVN HNNODHV Table 3 f m 0 g0 05 g at G lt1 6quot61 G a x 2 x 121 x121quot 4 2 12 12 12 14 18 332 3n2 g 114815 1 n x f G x oz 5 m 0 30 2 386861 10 l 29 142321 328118 9 2 2341439 0048 5487 0946965 341439 225 23929309 3 2114837 0000775386 0295811 114837 0768237 34800082 4 20118941 988848 8 00298239 0118941 00980241 38702061 5 2000351611 763957 14 0000879106 000351611 000341469 39877511 6 200000104590 598310 24 261474 6 104590 5 104552 5 39996473 8Z 6 END 393 CRIVHOIH a An edlted MATLAB reference card realmln a Smallest posltlve floatlng polnt numberv pl 4 3 1415925535897HH gtgt help 1 3 a Imaglnary unltv HELP toplcsz NaN 4 NotaaaNumberv lsnan a True for NotaaaNumberv matlahgeneral a General purpose commands lslnf a True for 1Df1n1te elements matlahops a Operators and speclal characters 1Sf1n1te a True for flnlte elements matlahlang a Programmlng language constructs flops a Floatlng polnt operatlon counts matlabspecfun a Speclallzed math functlons gtgt help elfun matlabdatafun a Data analysls and Fourler transforms Elementary math functlons matlabfunfun a Eunctlon functlons and ODE solvers Trlgonometrlcv matlabsparfun a Sparse matrlces sln a Slnev matlahgraph2d a Two dlmenslonal graphs Slnh a Hyperbollc Slnev matlahgraph3d a Three dlmenslonal graphs asln a Inverse Slnev matlahspecgraph a Speclallzed graphs aslnh a Inverse hyperbollc Slnev matlahgraphlcs a Handle Graphlcs cos a Coslnev matlahultools a Graphlcal user Interface tools cosh a Hyperbollc Coslnev matlabstrfun a Character strlngs acos a Inverse Coslnev matlablofun 4 F116 luputoutputv acosh a Inverse hyperbollc Coslnev matlabtlmefun a Tlme and dates tan a Tangent matlabdatatypes a Data types and structures tanh a Hyperbollc tangent matlahdemos 4 Examples and demonstratlons atan a Inverse tangentv atan2 a Four quadrant lnverse tangent Eor more help on dlrectorytoplc type quothelp toplc39u atanh a Inverse hyperbollc tangentv sec 4 Secantv sech a Hyperbollc secantv gtgt help elmat csc a Cosecantv csch a Hyperbollc cosecantv Elementary matrlces and matrlx manlpulatlonv cot a cotangent coth a Hyperbollc cotangent Elementary matrlces zeros a Zeros arrayv Exponentlalv ones a Ones arrayv exp 4 Exponentlalv eye a Identlty matrlxv log a Natural logarlthmv repmat a Repllcate and tlle arrayv loglo a Common base 10 logarlthmv rand a Unlformly dlstrlhuted random numbers sqrt 4 Square rootv randn 4 Normally dlstrlhuted random numbers llnspace a Llnearly spaced vectorv Complexv logspace a Logarlthmlcally spaced vectorv abs 4 Absolute valuev meshgrld a x and Y arrays for 340 plots angle a phase angle a Regularly spaced vector and Index lnto matrlxv Con a Complex conjugate Baslc array Informatlonv real 4 Complex real party Slze a 126 of matrlxv lsreal a True for real arrayv dlsp a Dlsplay matrlx or text Roundlng and remalnderv lsempty a True for empty matrlxv flx a Round towards zerov lsequal a True 1 arrays are 1dentlcalv floor a Round towards mlnus 1Df1n1tyv 1Snumerlc a True for numerlc arrays Cell a Round towards plus 1Df1n1tyv 1sloglcal a True for loglcal arrayv round a Round towards nearest Integerv loglcal 4 Convert numerlc values to loglcalv mod 4 Modulus slgl39led remalnder after dlvlslony rem a Remalnder after dlvlslonv Matrlx manlpulatlonv 51911 a Slgrlumv reshape a Change Slzev hag a Dlagonal matrlces and dlagonals of matrlxv trll 4 Extract lower trlangular parts gtgt help lang trlu 4 Extract upper trlangular parts fllplr a Fllp matrlx 1n leftrlght dlrectlonv Programmlng language constructs fllpud a Fllp matrlx 1n updown dlrectlonv flnd a Flnd 1ndlces of nonzero elements Control flowv end a Last 1ndexv It a Condltlonally execute statements subZlnd a Llnear Index from multlple suhscrlpts else 4 IE statement Condltlonv 1nd25ub a Multlple subscrlpts from llnear 1ndexv lself 4 IE statement Condltlonv nd a Termlnate scope of EOR WHILE SWITCH and IFV Speclal varlables and constants for 4 Repeat statements a Speclflc number of tlmes ans 4 Most recent answerv whlle 4 Repeat statements an 1ndef1n1te number of tlmes eps a Floatlng polnt relatlve accuracyv break a Termlnate executlon of WHILE or FOR loops realmax a Largest posltlve floatlng polnt numberv swltch a Swltch among several cases based on expresslonv e e case A SWITCH Statement cases punct A Contlnuatlon otherwlse 4 Default SWITCH Statement cases return a Return to lnyoklng functlonv punct a Asslgnment Evaluatlon and executlonv punct a Quote eyal a Execute strlng wlth MATLAE expresslonv transpose a Transpose J feval a Execute functlon Speclfled by Strlngv ctranspose a Complex conjugate transpose run a Run Scrlptv Scrlpts functlons and varlablesv gtgt belp matfun a About MATLAE scrlpts and Mafllesv functlon a Add new functlonv global a Deflne global varlablev mfllename a Name of currently executlng Mafllev exlst 4 Check 1 varlahles or functlons are deflnedv 1sglobal a True for global varlablesv Matrlx functlons a numerlcal llnear algebrav Matrlx analyslsv norm 4 Matrlx or vector norms Argument handllngv null a Null spaces nargcbk a Valldate number of lnput arguments nargln a Number of functlon lnput arguments nargout a Number of functlon output arguments Llnear equatlonsv and a Llnear equatlon solutlon use 39help slash39 lny a Matrlx 1nversev cond a Condltlon number wlth respect to luverslonv cbol a Cbolesky factorlzatlonv lu a LU factorlzatlonv Message dlsplayv error a Dlsplay error message and abort functlonv warnlng a Dlsplay wamlng messagev Elgenvalues and slngular values 619 a Elgenvalues and elgenvectorsv sprlntf a erte formatted data to a Strlngv poly a Characterlstlc polynomlalv Interactlve lnputv condelg a Condltlon number wlth respect to elgenvaluesv lnput a Prompt for user lnputv keyboard a lnyoke keyboard from Mafllev pause 4 Walt for user responsev Matrlx functlonsv expm a Matrlx exponentlalv logm a Matrlx logarlthmv sqrtm a Matrlx square root gtgt belp ops funm 4 Evaluate general matrlx functlonv Operators and speclal characters gtgt belp debug Arlthmetlc operators plus a Plus Debugglng commands dbstop a Set breakpolntv dbclear 4 Remove hreakpolntv dbcont a Resume executlonv 4lt4ltlt gt H tr a u E E gt I u o d m m E a u dbtype a Llst Maflle wlth llne numbers dbup a ange local workspace contextv kron a kronecker tensor product kron dbqult a Qult debug mode Relatlonal operators ge a Greater than or equal gta Loglcal operators and a Loglcal AND amp any a True 1 any element of vector 1s nonzero all a True 1 all elements of vector are nonzero Speclal characters colon a Colon V paren a Parentheses and subscrlptlng paren a Brackets

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.