### Create a StudySoup account

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

Already have a StudySoup account? Login here

# NUMERICAL ANALYSIS CS 537

UK

GPA 3.92

### View Full Document

## 17

## 0

## Popular in Course

## Popular in ComputerScienence

This 22 page Class Notes was uploaded by Juvenal Beahan on Friday October 23, 2015. The Class Notes belongs to CS 537 at University of Kentucky taught by Staff in Fall. Since its upload, it has received 17 views. For similar materials see /class/228218/cs-537-university-of-kentucky in ComputerScienence at University of Kentucky.

## Reviews for 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/23/15

C5537 Numerical Analysis and Computing Lecture 2 Locating Roots of Equations Professor Jun Zhang Department of Computer Science University of Kentucky Lexington KY 402060046 September 9 2008 I What is the Root l Many physical system can be written in the form of an equation This equation represents the relationship between the dependent variables and independent variables The root of a nonlinear equation is the solution of that equation It can also be said to the solution of a nonlinear system Most nonlinear equations are too complicated to have an analytical solution In practice we are more interested in finding some numerical solutions tXpllClt numbers apprOXImate SOIUIIOnS I Roots of a Functions I Letfx be a function that has values of opposite signs at the two ends of a given interval uu with u x u cfafb u ffx is continuous on ab then there exists a number c in ab such thatfc 0 c is called a root of functionfx 0 Example The function fx x2 2x 3 0 has a root in the interval 02 It has two roots in the interval 52 Remark roots are not necessarily unique in a given interval Need some root finding algorithms for general functions I Bisection Method I Given an interval ab and a continuous function x ifjajb lt 0 thenjx must have a root in ab How to find it We supposeja gt 0 andjb lt 0 lb l 2 ba Step 1 Compute the midpoint C 2 9 stop if is small and take c as the root Step 2 Evaluatejc ifjc 0 a root is found Step 3 If jc 96 0 then eitherjc gt 0 orjc lt 0 Step 4 fjc lt 0 a root must be in ac Step 5 Let b cfb fc go to Step 1 I Convergence Analysis I ab Let r be a root offx in the interval 10 b0 Let c0 be the midpoint then b a ltM Ir col 2 If we use the bisection algorithm we compute and have a0 b0 c0 a1 b1 c1 then bn a lr cnl S n n 2 2 Since the interval is halved at each step we have Hence ho a r cl S 2 which is the maximum error if we take cn as an approximate to the root r I Linear Convergence I A sequence xn has linear convergence to a limitx if there exists a constant C in the interval 01 such that lxn1 xl S Clxn xl n 2 1 By recursion we have xn1 xl S Clxn xl S C2xn1 x S S Cnlx1 xl Or equivalently a linear convergence satisfies an xl 3 AC 0 s C lt 1 For some positive numberA The bisection algorithm has a linear convergence rate with C 12 and Stopping Criterion What is our goal When to stop How many iterations Our goal is to find r 6 ab such thatjr 0 With bisection algorithm we generate a sequence such that r cn lt 8 For some prescribed number 6 gt 0 Le we find a point cn inside the interval 10 that is very close to the root r We then use on as an approximate to r It is not guaranteed however thatfc is very close to 0 How Many Iterations If we want the approximate root cn is close to the true root r ie we want 1 Cn lt 8 Then the number of bisection steps n satisfies b a 2n1 lt8 n gt logb a 10g28 10g 2 Example Find a root in 1617 up to machine single precision 21 10 00002 b 10 00102 so r must have a binary form r 10 1002 We have a total of 24 bits 5 is already fixed The accuracy will be up to another 19 bits which is between 23919 and 23920 We choose 6 1039 Since b a 1 we need An l39l gt A20 yielding n 2 20 I Newton s Method I Given a functionjx and a point x0 if we know the derivative offx at x0 we can construct a linear function that passes through x0jx0 with a slope m0 0 as lx f39xoxxofxo Since x is close tofx at x0 ifx0 is close to r we can use the root of x as an approximate to r the root offx x xo 1 0 f39xo x1 may not be lose to r enough we repeat the procedure to find fX1 x2 x1 f39x1 Under certain conditions xn converges to r IFrom Taylor Seriesl fjx0 96 0 but x0 is close to r we may assume that they differ by h ie x0 h r or fx0hfquot0 Using Taylor series expansions hz fxohf39xo7fquotxo 0 Ignoring the higher order terms we have Or fx0hf39xo 0 fxo f39xo Since h does not satisfyjx0 h 0 we use f 39xo as an approximate to r and repeat the process 10 Fast Converence Find a root for the following functionfx starting atxJ 4 fxx3 2x2x 3 f39x 3x2 4x 1 H E 27224 49386 01006 94102 O iO39lbLONDIO N M 0 o co 731445 143684 550714 932841 448 x 106 197 x 10H12 Each iteration gains double digits of accuracy andfxn decreases quadratically to 0 I Convergence Analysis I Let the functionf have continuous first and second derivativesj andj and r be a simple root off withf r 96 0 Ifx0 is sufficiently close to r then Newton s method converges to r quadratically X n1 2 x 4i d c Ifxn differs from r by at most one unit in the kth decimal place ie Ix rl S 1039k Then for c 1 we have ix 1 rl s 104quot The number of correct decimal digits doubles after another iteration 12 Converence Proof Let en r xn Newton s method gives a sequence xn such that xn r x r x 1 quot1 quot f39x fx ef39x 09 f 3909 f 3909 Using Taylor s expansion there exists a point En between xnand r for which 0 fr fxe xn enf39xe fquot n e n 9quot It follows that enf39xn xn e fquot n IConvergence Proof Cont We thus have en1 2 f xn Define an upper bound f quotx f 39 x l maXx VS 05 5 gt O 2 minl Isa We can choose 6 small so that lenl Ix r S 6 and lgquot r S 6 This is to guarantee that xn is close to r within a distance of 6 14 Convergence Proof Cont For very small 6 gt 0 we have le i1 n1 2 fquotrfn f39xn S 6 c6enl plenl With p 6c6 lt 1 if 6 is small enough therefore e S c6e lxn1rl len1l Sl lenl Slenl xn1 is also close to rwithin a distance of 6 By recursion ifx0 is close to r then le llt le llt 2le lltlt quotle l n p n l p n l p 0 Sincep lt 1 this is to say limlenl 0 as n oo n oo 15 I Weakness of Newton s Method I Newton s method converges fast only when x0 is chosen close to r In practice there might be a number of problems also 1 needs derivative value and availability 2 starting point must be close to r 3 lose quadratic convergence if multiple root 4 iterates may runaway not in convergence domain 5 flat spot withf xn 0 6 cycling iterates around r 16 Systems of Nonlinear Equations Newton s method is really useful for finding zero of a system of nonlinear equations f1x1x2xn0 f2x1xzxn0 fnx1x2xn 0 Written in vector form as fx0 Where f f2fnT x x1x2xnT Wehave xk1 xk P x00 1 1 fxk f xk Jxk is the Jacobian matrix 17 IA 3 Equation Examplel flxlx29x3 f2x19x2 x3 f3x19x2 x3 Using Taylor expansion fixl h1ax2 h29x3 h3 fix19x29x3 6x1 6x2 6x3 Let x0 xfox 0x 0T be an approximate solution and the computed correction be hh1h2h3T Hence 0 z fx0 h fx0 f39x0 h 18 Exam le Cont TheJacobian matrixis 0A if 1 6x1 6x2 6x3 af2 af2 6f2 6x1 6x2 6x3 6f3 6L3 6L3 6x 6x 6x Itfollowsthat 1 2 3 h z rx r1fx Hence the new iterate is x0 x0 f39x0 1fx0 In practice we solve the Jacobian matrix in Jxk hk fxk So that Xk1 X00 hltkgt 19 Secant Method In Newton s method mu 1 We need to evaluate xn andf xn at each iteration We can approximate the derivative atx xn by x x mu x x n l n Thus the secant method generates iterates xn xn l xn1 xn fxnfXn1 Only one functional evaluation at each iteration xn 20 Comments Secant method needs two iterates to start with can use bisection method to generate the second iterate Secant method does not need to know the derivative ofjx If jxn jxn1 is small the computation may lose significant digits and becomes unstable The convergence rate of secant method is superlinear a len1 S Clenl With a 1 J3 z 162 Its convergence rate is between that of bisection method and the Newton s method 20 Hybrid Approaches In practice hybrid methods are usually used For example we can use Bisection Method to generate initial iterates that are close to the root so that Newton s method can be applied We the evaluation of derivative is expensive the Secant Method should be used to replace the Newton s method The tradeoffs between Bisection Method and Newton s Method are robustness and fast convergence The Secant Method is supposed to come between these two methods to take the advantages of both and avoid the disadvantages of either

### 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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "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.