-
Newton's Method is a procedure for finding numerical approximations to ______ of functions. Why are numerical approximations important?
- zeros
- Its often impossible to find the zeros exactly
-
For example, the polynomial f(x) = x5 - x - 1 has one real root c (Fig. 1 pg 216), but we can prove, using an advanced branch of mathematics called _____ ______, that there is no algebraic formula for this root. Newton's Method shows that c ~ 1.1673, and with enough computation, we can compute c to any desired degree of accuracy
Galois Theory
-
In Newton's Method, we begin by choosing a number x0, which we believe is close to a root of the equation f(x) = 0. This starting value x0 is called the ______ ______. Newton's Method then produces a sequence x0, x1, x2,... of successive approximations that, in favorable situations, converge to a _______
-
Fig 2 (pg 217) illustrates the procedure. Given an initial guess x0, we draw the tangent line to the graph at (x0, f(x0)). The approximation x1 is defined as the x-coordinate of the points where the ____ ______ intersects the x-axis. To produce the second approximation x2 (also called the ______ _______), we apply this procedure to x1.
- tangent line
- second iterate
-
With the tangent line at (x0,f(x0)), derive a formula for x1.
y = f(x 0) + f'(x 0)(x - x 0)
- The tangent line crosses the x-axis at x1, where:
- y = f(x0) + f'(x0)(x1 - x0) = 0
- If f'(x0) ≠ 0, we can solve for x1 to obtain:
- x1 - x0 = -f(x0)/f'(x0), or x1 = x0 - [f(x0)]/[f'(x0)]
-
How would you obtain the second iterate x2?
**Notice in Fig 2 (pg 217) that x1 is closer to the root than x0 and that x2 is closer still. This is typical, (explain)
- By applying the formula to x1 instead of x0:
- x2 = x1 - [f(x1)/f'(x1)]
The successive approximations usually converge to the actual root. **However, there are cases where Newton's Methods fails
-
Newton's Methods is an example of an _______ procedure (define)
- iterative procedure
- To iterate means to repeat, and in Newton's Method, we use Eq.1 repeatedly to produce the sequence of approximation
-
State Newton's Method of approximating a root of f(x) = 0
- Step 1: Choose an initial guess x0 (close to the desired root if possible)
- Step 2: Generate successive approximations x1, x2,..., where
- xn+1 = xn - [f(xn)/f'(xn)]
-
How many iterations of Newton's Method are required to approximate a root to within a given accuracy?
There is no definitive answer, but in practice, it is usually safe to assume that if xn and xn+1 agree to m decimal places, then the approximation xn is correct to these m places
-
Sometimes, Newton's Method computes no root at all. In Fig 4 (pg 218), the iterates diverge to ______. In practice, however, Newton's Method usually converges quickly, and if a particular choice of x0 does not lead to a root, the best strategy is to try a ______ ______ ______, consulting a graph if possible. If f(x) = 0 has more than one root, different ______ _____ x0 may lead to different _______
- infinity
- different initial guess
- initial guesses x0
- roots
|
|
