Newton-Raphson Method

· This method is used to find a solution p to the equation f(x)=0. This method uses the extra information provided by f’(x) and f’’(x) to generate a sequence {p_k} that converges to p faster then the Bisection or Regula Falsi methods. The value of p_k is determined by the intersection of f’(p_k-1) and the x axis. It requires that f(x), f’(x), and f’’(x) are continuous.

Generating the Iteration Function: The value of p_k is determined by the intersection of f’(p_k-1) and the x axis.

Setting these equal …

Newton-Raphson and Taylor Polynomials

Taylor polynomials are used to approximate a continuous function using a polynomial.

Newton-Raphson approximates f(x) using the taylor expansion up to the first two terms. If we set p₁=x and f(p₁)=0 …

This is the same result as above. If we use more then 2 terms, then we are approximating f(x) by a curve, which would improve the rate of convergence of Newton-Raphson, but require computing the appropriate derivatives, as well as all the appropriate derivates be continuous.

Some General Notes

· Newton-Raphson is a fast method, but it requires the derivate of the equations as an input, however, it is possible in most cases to computer the derivative numerically.

· . If we choose ε carefully i.e. small enough, the numeric approximation of the derivative should work. For example, given f(x)=sin(x)-.5; the range of y is [-1.5,.5]. If we choose ε=.001, then ε is only 0.05% of the range, which for x=.5 is accurate to 3 decimal places.

· In some cases, it is useful to have ε change between iterations.

· When using these methods, f(p_k)→0 is an obvious, but useful, sanity check.

An Example of the Newton-Raphson Method

The exact answer is .5235 radians.

Iteration	p_k	f(p_k)	f’(p_k)	p_k+1
0	p₀=0	sin(0)-.5=-.5	cos(0)=1	0-(-.5/1)=.5
1	p₁₌.5	sin(.5)=-.02	cos(.5)=0.8775	.5-(-.02/0.8775)=0.522
2	p₂₌.522	-0.00139	0.8668	.5235
3	p₃₌.5235

Secant Method

This method is convenient when a method with a rate of convergence near to that of Newton’s Method is wanted, however calculating f’(x) is problematic. It is very similar to the regula falsi method. Two points are chosen on f(x), and we generate a third point by taking the intersection of this line and the axis and applying the function to that point. This point and the previous one are now used to generate a new line.

Generating the Iteration Function

Setting these equal…

Generating Newton-Raphson from the Secant Method

Examining the term, if

Substituting back into the Secant Method, we get

which is the Newton-Raphson iteration function.

An Example of the Secant Method

The exact answer is .5235 radians.

Iteration	p_k	f(p_k)	p_k+1
0	0	-0.5
1	1	0.3415	1 - [.3415(1-0)] / (.3415 + .5) = .594
2	.594	.0597	.594 – [.0597(.594-1)] / (.0597-.3415) =
3	.50799	-.0136	.5239

Order of Convergence

· Order of Convergence is a measure of how fast a method converges to the solution.

· If R=1, the convergence is said to be linear. If R>1, the solution is said to be quadratic.

Order of Convergence for Covered Numerical Methods

· Newton Raphson (one root) : : quadratic convergence

· Newton Raphson (m roots) : : linear convergence.

· Secant Method (one root) : : R = 1.618

· Secant Method (two roots) : R = 1

· Bisection Method : R = 1, A = ½.

· Regula Falsi : R = 1.

Linear Algebra Review

· An n-dimensional vector x=(x₁ , x₂, x₃ , …, x_n) represents a point in an n-dimensional space.

· An n-dimensional space is the set of all n-dimensional vectors.

· A vector used to describe a position is called a position vector

· A vector used to describe a displacement between 2 points is called a displacement vector.

Operations

x, y are vectors. c,d are scalars.

Scalar Multiple :

Linear Combination :

Euclidean Norm (magnitude of the vector) :

Distance Between 2 Points :

Dot Product :

Vector Algebra

x,y,z are vectors. a,b are scalars.

x + y = y + x Communitive Property

x + 0 = x Additive Identity

x – x = x + (-x) = 0 Additive Inverse

(x + y) + z = x + (y + z) Associative Property

x(a + b) = ax + bx Scalar Distributive Property

a(x + y) = ax + ay Vector Distributive Property

a(bx) = (ab)x Scalar Associative Property

Linear Systems

Each equation represents a plane in 3-space. The solution is the intersection of the 3 planes. The system can also be represented using a matrix an a vector :