• 7/7/2003
  • Newtons Method for solving non-linear systems
  • Taylor Expansion for Interpolation and Polynomial Approximation
  • Horner's Method for evaluating polynomials (also called Nested Multiplication)
• 7/8/2003
• 7/9/2003
• 7/10/2003
  • Pade Approximation for Polynomial Approximation
  • Example Part a of Pade Approximation
  • Example Part b of Pade Approximation
• 7/11/2003
  • Least Squares Line For Curve Fitting
  • An Example of Least Squares
  • Using a Curve for Curve fitting

7/7/2003

Solutions of Non-linear Equations

Newton’s Method

• Extend Newton-Raphson method to equation with 2 variables
• Assume the Taylor expansion around x0,0 in function with 2 variables
• 
• Example of Newton's Method:
  • f₁(x,y) = x²-y-.2 = 0
    
  • f₂(x,y) = y²-x-.3 = 0
  • 

Interpolation and Polynomial Approximation
--We Want to approximate functions using polynomials
--Used to computer other functios such as sin(x), cos(x), etc.
Taylor Expansion

• Expresses a function with a polynomial of the form
• 
• If we want to approximate the fuction using a polynomial of degree N
• 
• Disadvantages
  • Higher order derivatives must be know and maybe hard to compute

• f(x) = x⁴ + 2x³ + 3x² + 2x
  • This as 9 multiplications
• f(x) = (((x+2)x+3)x+2)x+1
  • But this only has 3 multiplications

7/8/2003 Methods for evaluating Polynomials

Lagrange Approximation

• Assume 2 points (x₀,y₀) and (x₁,y₁), let's build the line that passes through these points.
  • m = (y₁-y₀)/(x₁-₀) = (y-y₀)/(x-₀)
  • y = y₀ + (x-x₀)(y-y₀)/(x₁-x₀)
• Lagrange used a different method to obtain this polynomial.
  • P₁(x) = y = y₀((x-x₀)/(x₀-x₁)) + y₁((x-x₀)/(x₁-x₀))
  • From y₀((x-x₀)/(x₀-x₁)) you get (1) x = x₀ and (0) x = x₁
  • From y₁((x-x₀)/(x₁-x₀)) you get (0) x = x₀ and (1) x = x₁
  • P₁(x) = y₀(1) + y₁
• The terms L_1,0 = (x - x₁)/((x₀-x₁) and L_1,1 = (x - x₀)/((x₁-x₀) are called "Lagrange Polynomials"
• The same idea can be used for polynomials of degree 2,3,...,n
• P₂(x) --> (x₀,y₀), (x₁,y₁), and (x₂,y₂)
  • P₂(x) = y₀((x-x₁)(x-x₂))/((x₀-x₁)(x₀-x₂)) + y₁((x-x₀)(x-x₂))/((x₁-x₀)(x₁-x₂)) + y₂((x-x₀)(x-x₁))/((x₂-x₀)(x₂-x₁))
• In general:
  • 
• Example:
  • 

7/9/2003 Methods for evaluating Polynomials

Newton Polynomial Approximation

• In Lagrange, p_n-1(x) and p_n(x) are not related
• Newton Polynomials can be built incrementally so p_n-1(x) can be used to build p_n(x)
  • p₁(x) = a₀ + a₁(x-x₀)
  • p₂(x) = a₀ + a₁(x-x₀) + a₂(x-x₀)(x-x₁)
  • p₃(x) = a₀ + a₁(x-x₀) + a₂(x-x₀)(x-x₁) + a₃(x-x₀)(x-x₁)(x-x₂)
  • p_n(x) = a₀ + a₁(x-x₀) + . . . + a_n(x-x₀)...(x-x_n-1)
• How to build P_n(x)
• Assume we want to build P₁(x) that passes through the points (x₀,f(x₀)) and (x₁,f(x₁))
  • p₀(x) = f(x₀)

7/10/2003
Polynomial Approximation Continued

Pade Approximations

• They are qutients of polynomials that are used to approximate functions:
  
  • R_n,m = (P_n(x)) / (Q_m(x))
  • Where 1) P_n(x) = p₀ + p₁x + p₂x² + . . . + p_nxⁿ
  • Where 2) Q_m(x) = 1 + q₁x + q₂x² + . . . + q_mx^m
• The polynomials are constructied so f(X) and R_n,m agree at x = 0 and also their derviatives agree at (up to N+M) x = 0
  
  • 3) f(x) * Q_m(x) - P_n(x) = Z(x)
• Where z(x) is the error function and z(x) goes to zero if:
  • f(x) = R_n,m
• Assume that f(x) has Taylor Expansion around x = 0 (Maclavin expansion:)
  • 4) f(x) = a₀ + a₁x + a₂x² + . . . + a_kx^k
• Substitute (4) f(X), (1) P_n(x), and (2) Q_m(x) into (3):
  • (a₀ + a₁x + a₂x² + . . . + a_kx^k)(1 + q₁x + q₂x² + . . . + q_mx^m) - (p₀ + p₁x + p₂x² + . . . + p_nxⁿ) = C₀x⁰ + C₁x¹ + . . . + C_n+mx^n+m
• We want the C₀x⁰ + C₁x¹ + . . . + C_n+mx^n+m to go to 0
• Performing multiplications of polynomials and factoringto make left side as small as possible
  • (a₀-p₀) + x(a₁+q₁a₀-p₁)+x²(a₂+q₁a₁-q₂a₀-p₂) + . . . = C₀x⁰ + C₁x¹ + . . . + C_n+mx^n+m
• The intial coefficents can be:
  • Node 0 a₀-p₀ = 0
  • a₁+q₁a₀-p₁ = 0
  • . . .
  • q_ma_n-m + q_m-1a_n-m-1 + . . . + a_n-p_n = 0
  • . . .
  • q_ma_n-m+1 + q_m-1a_n-m+2 + . . . + a_n+1= 0
  • q_ma_n + q_m-1a_n+1 + . . . + q_n+M= 0
  • We get N+m+1 equations and we have N+m+1 variables to compute. Solve first the last 2 equations and you will get the polynomials P and Q.

• Start with Maclauren expansion:
  • f(X) = 1 - (x/2) + (x²/3) - (x³/4) + (x⁴/5) + . . .
  • R_N,M(x) = (P_N(x)) / (Q_M(x))
  • R_2,2(x) = (P₂(x)) / (Q₂(x))
• From that we get:
  • R_2,2(x) = (P₀ + P₁x + P₂x²) / (1 + q₁x + q₂x²)
• Now you must put it into the form f(x)*(Q_M(x))-(P_N(x)) to get:
  • x * (1 - (x/2) + (x²/3) - (x³/4) + (x⁴/5) + ...)(1 + q₁x + q₂x²) - (P₀ + P₁x + P₂x²) = 0
    Multiply through to get :
  • (1 - (x/2) + (x²/3) - (x³/4) + (x⁴/5) + q₁x - (q₁x²)/2 + (q₁x³)/3 - (q₁x⁴)/4 + (q₂x²) - (q₂x³)/2 + (q₂x⁴)/3) - (P₀ + P₁x + P₂x²) = 0
• From here you obtain 5 equations (By some algebra work)
  • (A) 1-p₀ = 0
  • (B) -.5 + q₁ - p₁ = 0
  • (C) (1/3) - (q₁)/2 + q₂ - p₂ = 0
  • (D) (-1/4) + (q₁)/3 - (q₂)/2 = 0
  • (E) (1/5) - (q₁)/4 + (q₂)/3 = 0
• To solve q₁ and q₂ multiply (D) by 3 and (E) by 4 and add (D) and (E) together.
• This results in: (1/20) - (q₂)/6 = 0 therefore q₂ = (3/10)
• Next plug q₂ into (D) and you get q₁ = (6/5)
• Then plug q₂ and q₁ it (C) and you obtain p₂ = (1/30)
• Plug q₁ into (B) and you get p₁ = (7/10)
• From (A) you have p₀ = 1
  • R_2,2(x) = (P₀ + P₁x + P₂x²) / (1 + q₁x + q₂x²)
    Plug in values:
  • R_2,2(x) = (1 + (7/10)x + (1/30)x²) / (1 + (6/5)x + (3/10)x²)
    For x=1
  • R_2,2(x) = (1 + (7/10)(1) + (1/30)(1)²) / (1 + (6/5)(1) + (3/10)(1)²) = .6933

• ln(1+x)/x = R_2,2(x) -----> ln(1+x) = R_2,2(x) * x
• x * ((1 + (7/10)x + (1/30)x²) / (1 + (6/5)x + (3/10)x²))
  Multiply the x through to get:
• (x + (7/10)² + (1/30)x³) / (x + (6/5)x² + (3/10)x³)
  Multiply by (30/30) to get rid of the fractions and you find that ln(x + 1) is approximately equal to:
• (30x + 21² + x³) / (30x + 36x² + 9x³)

7/11/2003

Curve fitting
Given a set of points (x₀,y₀)...(x_n,y₀) come up with a curve that best fits the points.
In polynomial approximation the polynomial passes through all points, but in curve fitting it does not pass through all points but atleast close to them.
Ex: An experimental procedure gives a set of points and you would like to obtain a function y = f(x) that relates all the points. Least Squares Line

• Assume that you have recorded the points (x₀,y₀)...(x_n,y₀) and we want to find the line y = Ax + B that best fits the recorded data.
• We have:
  • f(x) = y = Ax + B
• We can express the approximation error as the distance from the line to the point:
  • e_k = f(x_k) - y_k
• There are several norms that we can use to tell us how far the curve f(x) is from the data.
  • 
• Given the points (x₀,y₀)...(x_n,y₀) the least square line y = f(x) = Ax + B is the line that mimizes the square error (3) we want to minimize this error so we apply te partial derivatives wit respect to A,B
  • 
• Solve (1) and (2) to Obtain A,B for the line y = Ax + B that best fits the data.

• Using (1):
  • 1043A + 67B - 155 = 0 (3)
• Using (2):
  • 67A + 5B - 17 = 0 (4)
• Multiply (3) by -5 and (4) by 67 and add them together to get:
  • -726A - 364 = 0 ----> A = -.5014
• Plug A into (3) to get:
  • (1043)(-.5014) + 67B - 155 = 0 ----> B = 10.11
• Thus:
  • f(x) = -.5014x + 10.11

• Sometimes however, 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 error so we take the partial derivative with respect to A
• 

• y = f(x) = Ax³
• Given x_k and y_k solve for the other variables you need:

• Plug in the values to get:
  • A = (10227.44) / (2056.28) ----> A = .5969
• Thus y = f(x) = .5969x³