Newthon’s method for solving of non linear equation

exc: f1(x,y)=x^2 –y -.2=0

f2(x,y)=y^2-x-.3 =0

-We extend Newthon Raphson method to equation with 2 variables

- We assume the Taylor expansion around xo,yo in function with 2 variables.

f1(x,y)=f1(x0,y0)+d/dx f1(x0,y0) (x-x0)+ d/dy f1(x0,y0)(y-y0)

f2(x,y)=f2(x0,y0)+d/dx f2(x0,y0) (x-x0)+ d/dy f2(x0,y0)(y-y0)

Expressing these 2 function in matrix form

[f1(x,y) ] =[f1(x0,y0)] +[ d/dx f1(x0,y0) + d/dx f2(x0,y0)] [x-x0]

[f2(x,y) ] [f2(x0,y0)] [d/dy f1(x0,y0) + d/dy f2(x0,y0)] [y-y0]

(J) jacobian

x->x1 and y->y1

[x1]= [x0] _ J^-1_(x0,y0) [f (x0,y0)]

[y1] [y0] [f2(x0,y0)]

f1(x,y)=x^2 –y -.2=0

f2(x,y)=y^2-x-.3 =0

J= [2x -1] J^-1=[2y 1] 1

[-1 2y] [1 2x] 4xy-1

start with x0=0.y0=0

• -x0=o y0=0 f1(x0,y0)=-0.2

f2(x0,y0)= -.3

J^{-1 =} 0 -1

-1 0

x1= -.3

y1= -0.2

• x1= -.3, y1= -0.2 f1=0.09 f2=0.04

J^-1 =[-0.4 1 ] 1 =. [0.326 -1.3157]

[ 1 -0.6 ] .24-1 [-1.3157 0.7895 ]

x2=-0.2947

y2=-0.113158

Interpolation and Polynomial approximation

- we want to approximate functions using polynomial

- -used for example to compute other functions such that sin(x),cos(x),e^x

Taylor Expansion

The taylor expansion expresses a function with polynomial of the form

f(x)= ∑_k=0^∞ f^(k)(x0) (x-xo)^k /k!

If we want to approximate the function using a polynomial of degree as

f(x)=Pn(x)= f(x)= ∑_k=0^∞ f^(k)(x0) (x-xo)^k /k!

f(x)=Pn(x)≠En(x)

En(x)=Fn+F(c)/(n+1)! for some c such that c lies between x and x0

e^x approximate using a polynomial of degree 3

Assume x0=0

f(x)=e^x f(0)=1

f’(x)=e^x f’(0)=1

f’’(x)=e^x f’’(0)=1

f’’’(x)=e^x f’’’(0)=1

f(x)=1/1(1)+1/1(x)^1 +1/2(x)^2+1/6(x)^3....

Disadvantages of Taylor expansion

The problem is that higher order derivatives must be known and maybe hard to compute.

Method for evaluating polynomials

Horner’s method/nested multiplication

f(x)=x^4+2x^3+3x^2+2x+1

f(x)=(((x+2)x+3)x+2)x+1

Suppose that a function f(x) is known to have N+1 points (x0,y0),(x1,y1),...(xN.yN)

such that a<=x0<x1<x2<...<xN<b and yk=f(xk)

We want to construct a polynomial p(x) of degree N that passes through these N+1 points.

The polynomial can be used for interpolation

If x0<x<x_N, the approximation is P_N(X)

extrapolation:

if x<x0 or x_N <x, P_N(x) is the extrapolated value.

Lagrange approximation

Assume 2 pts (x0,y0),(x1,y1) . Lets build the line that passes through these 2 points.

m=(y1-y0)/(x1-x0)= ((y-y0)/(x-x0)

y=y0+(x-xo)(y-y0)/(x1-x0)

Lagrange used a differnt method to obtain this polynomial

This line can be written

p1(x)=y=y0(x-x1)/(x0-x1)+y1(x-xo)/(x1-x2)

p1(x0)=y=y0(x0-x1)/(x0-x1)+y1(x0-xo)/(x1-x0)=y0

p2(x1)=y1

The terms :

L_1,0 =(x-x1)/(x0-x1) and L₁₁=(x-x0)/(x1-x0)

are called “lagrange polynomials”

The same idea can be used for polynomials of degree2,3,..N

In general:

Pn(x)= ∑_k=0 ^N Y_k L_n,k (x)

Ln,k(x)= ∑_j=0j!=k ^N (x-xj)

∏ _j=0j!=k ^N (xk-xj)

exc:

We want to approximate sin(x) in the interval 0, pi/2 with a polynomial of degree 3

x sin(x)

0 0

pi/6 .5

pi/3 .866

pi.2 1

p3(x)=0.7054

sin(pi/4)=0.7071

error=|.7071-0.7054| /1.7071 =0.2%

Newthon Polynomial

In lagrange polynomial, P_n-1(x) and Pn(x) are not related. Newton polynomial can be built incrementally, so P_n-1(x) can be used to build Pn(x)

Newthon polynomial

P0(x)=a0

P1(x)=a0+a1(x-x0)

p2(x)=a0_a1(x-x0)+a2(x-x0)(x-x1)

=p1(x)+a2(x-x0)(x-x1)

;

;

Pn(x)=a0+a1(x-x0)+...+an(x-x0)...(x-xn-1)

How to compute a0,a1,...an

Assume we want to build p1(x) that passes through the points (x0,f(x0)) and (x1,f(x1))

p0(x0)=f(x0) p1(x1)=f(x1)

p1(x0)=a0_a1(x0-x0)=f(x0)

p1(x1)=a0+a1(x1-x0)

f(x1)=f(x0)+a1(x1-x0)

a1=(f(x1)-f(x0))/(x1-x0)

exc: Build polynomial p1(x), p2(x), p3(x) that approximate f(x)=sin(x) in the interval 0,pi/2

xk f(xk) f[xk-1,xk]

x0 0 sin(0)=0 (.5-0)/(0.5236-0)=.9544 (a1)

x1 pi/6=0.5236 sin(pi/6)=.5

x2 pi/3=1.047 .8659 (0.8659-0.5)/(1.047-0.5236)=.699

x3 pi/2=1.5708 ½ (1-0.869)/(1.5708-1.047)=0.256

f[xk-2,xk-1,xk] f[Xk-3,xk-2,xk-1,xk]

(.699-0.09549)/(1.047-0)=-.2404 (-.4230+0.244)/(1.5708-0)=-.1137

(.256-0.699)/(1.5708-0.5236)=-0.4230

p1(x)=0+0.9549(x-0)=0.9549x

p2(x)=0.9549x+(-.2444)(x-x0)(x-x1)

p3(x)=0. .9549x+(-.2444)(x-x0)(x-x1)-0.1137(x-x0)(x-x1)(x-x2)

sin(pi/4)=0.7071

p1(.7854)= 0.9549(.7854)=.74998

p2(.7874)=.6997

p3(.7874)=.70582

Pade’s Approximation

There are qutients of polynomial that are used to approximate functions:

Rn,m(x)=Pn)x_/Qm(x) for a<=x<=b

Where

1 --Pn(x)=P0+P1 X+P2 X^2 + Pn X^n

2---Qm(x)=1+Q1 X +Q2 X^2 +….Qm X^m

The polynomials are constructed so f(x) and Rn,m(x) agree at x=0 and also the derivatives agree at x=0 (up to M ≠N)

We want

F(x) = Pn,m (x)= Pn(x)/Qm(x)

3---F(x) Qm(x)=Pn(x)=z(x)

Assume that f(x) has the Taylor expansion around x=0 (Ma Claurin expantion)

4---F(x)=a0+a1 X+a2 X^2 +…. Ak X^k+…

Substitute f(x) in 3 and also function 1 and 2

F(x) Qm(x)-Pn(x)= C0 X^0 +C1 X+…. Cn+m X^(n+m) =0

Performing multiplication of polynomial and factoring

(a0-p0)+x(a1+q1(a0-p1))+x^2(a2+q1a1+q2(a0-p2))+…=c0x^0+c1X+c2x^2+…

To make the left side as small as possible the initial coefficeient can be 0.

A0-p0=0

Q1a0+a1-p1=0

Q2a0+q1a1+a2-p2=0

;;;

qm+n + qm-1qn+1….qn+m=0

we get n+m+1 equations and we have n+m+1 variables to computer.

Exc:

Find the Pede’s approximation R2,2 (x) for f(x)=ln(1+x)/x start with the maclurin expansion

F(x)=1 –x/2+x^2 /3 -…

Solution

Rn,m(x)=Pn(x)/Qm(x)

R2,2(x)=P2(x)/Q2(x)= (P0+P1X+P2X^2)/(1+Q1X+Q2X^2)

We want f(x)Qn(x)-Pn(x)=0

(1 –x/2+x^2 /3 -…)(1+Q1X+Q2 X^2)-(P0+P1X+P2X^2)=0

1-x/2 +x^2 /3 - x^3 /4 +….

Q1x -Q1 /2 x^2 +q1/3 x^3 -………..

;

;

-p0-p1 x –p2 x^2 =0

1-p0=0

-1/2+q1-p1=0

1/3-q1/2+q2-p2=0

-1/4+q1/3-q2/2=0

1/5-q1/4+q2/3=0

p2=1/30

p1=7/10

p0=1

q1=6/5

q2=3/10

R2,2(x)=(1+7/10x+1/30x^2)/(1+6/5x+3/10x^2)

For x=1 (ln(1+x))/x =.6931

R2,2=.6933

Given the approx for ln(1+x)/x obtain an approximation for ln(1+x)

(ln(1+x))/x =R2,2(x)

ln(1+x)=x R2,2(x)=x. ((1+7/10x+1/30x^2)/(1+6/5x+3/10x^2))

=(30x+21x^2+x^3)/(36+36x+9x^2)

CURVE FITTING

Given a set of points (x0,y0)(x1,y1)….(xn,yn) come up with the curve that best fit these points.

Polynomial Approximation –Polynomial passes through all points.

Curvefitting-curve does not necessarily passes through the points but it passes cloes to them.

Exc, An experimental procedure gives a set of tpoints and you would like to obtain a function y=f(s) that relates the points.

Least Square line

Assue that you have recorded the points(x0,y0,..(xn,yn)

And we want to find the line y=Ax+B that best fits the recorded data. We have that f(x)=y=Ax+B

We can express the approximation error as ek=f(xk)-yk

There are several norms that can be used to tell us how far the curve f(x) is form the data

Max error E_inf (f)=max _1<=k<=n {|f(xk)-yk|}

Average error E1(f)=1/N ∑_k=1 ^N {|f(xk)-yk|}

Rott mean Square Error E₂(f)=1/N ∑ _k=1 ^N (f(xk)-yk)^2

Given the points (x1,y1)(x2,y2)..(xn,yn)

The least square liney=f(x)=Ax+B is the line that minimized the root mean square error E2(f).

we want to minimize this error so we apply partial derivatives with respect to A and B.

∂E(A,B)/∂A=1/N ∑_k=1 ^N 2(Axk+B-Yk)Xk

=A ∑_k=1 ^N Xk^2+B∑_k=1 ^NXk^-∑_k=1 ^NxkYk= 0 ---1

∂E(A,B)/∂B=1/N ∑_k=1 ^N 2(Axk+B-Yk)

= A ∑_k=1 ^N Xk+BN^-∑_k=1 ^NYk= 0----(2)

Solve 1 and 2 to obtain A and B for the line Y=Ax+B that best fits the data.

Exc: data

Xk Yk Xk^2 Xk Yk

1 6 7 36 42

2 9 6 81 54

3 14 3 196 42

4 17 1 289 17

5 21 0 441 0

67 17 1043 185

Obtain the line Y=Ax+B that best fits the data

From (1) A 1043+67B-135=0

From (2) 67A+5B-17=0

F(x)=- .5613 x +10.11

Sometimes instead of fitting to a function f(x)=Ax+B, we would like to fit the data points to the curve f(x)=AX^M where M is known and A is unknown.

We also want to minimize the square erroe

E(A)= A ∑_k=1 ^N (Axk^M-Yk)^2

∂E(A,B)/∂A= ∑_k=1 ^N 2(Axk^M-Yk)Xk^M=0

A= ∑_k=1 ^N (Yk Xk^M/∑_k=1 ^N Xk^(2M))

Exc: y=Ax^3

Xk Yk XkYk^3 Xk^6

2 5.9 47.2 64

2.3 8.3 100.86 14.86

2.6 10.7 1888.06 308.92

2.9 13.7 334.13 599.32

3.2 17 557.66 1075

1227.44 2056.2

A=1227.44/2056.28 =.5969

Y=.5969X^3