July 5^th , 2004

*No Class

July 6^th , 2004

*Midterm – 7:00-9:00pm - Wednesday, July 14^th – WHTR 104

*Homework 3 – “Prep for Midterm” – Due Tuesday 13^th in class

Example from July 2^nd continued:

Ex. Build degree 1, 2, and 3 polynomials to approximate f(x) = sin(x) over the interval (0, π/2)

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₀)

x₀ = 0 x₁ = π/6 x₂ = π/3 x₃ = π/2

x_k f(x_k) f(x_k-1,x_k) f(x_k-2,x_k-1,x_k) f(x_k-3,x_k-2,x_k-1,x_k)

--- ------ ----------- ---------------- ---------------------

0 0 ßa₀

π/6 0.5 0.9549 ßa₁

π/3 0.8659 0.699 -0.244 ßa₂

π/2 1 0.236 -0.4230 -0.1137 ßa₃

P₁(x) = x₀ + a₁(x - x₀) = 0 + 0.9549(x – 0) = 0.9549x

P₂(x) = a₀ + a₁(x - x₀) + a₂(x – x₁)(x – x₀) = P₁(x) + a₂(x – x₁)(x – x₀) = 0.9549x -0.244(x – 0)(x - π/6)

= 0.9549x – 0.244x² + π/6(0.244)x = -0.244x² + x(0.9549 + 0.244(π/6))

P₃(x) = a₀ + a₁(x - x₀) + a₂(x – x₁)(x – x₀) + a₃(x – x₂)(x – x₁)(x – x₀) = P₂(x) + a₃(x – x₂)(x – x₁)(x – x₀)

= -0.244x² + x(0.9549 + 0.244(π/6)) – 0.1137(x(x - π/6)(x - π/3))

Assume: x = π/4 = 0.7854 sin(π/4) = 0.7071

P₁(π/4) = 0.749978

P₂(π/4) = 0.749978 + 0.244(0.9854)(0.7854 – 0.5236) = 0.699725

{ adjustment }

P₃(π/4) = 0.699725 + (-0.1137)(0.7854 – 0)(0.7854 – 0.5236)(0.7854 – 1.047) = 0.705841

{ adjustment }

* P₃(π/4) is very close to the actual solution!

July 7^th , 2004

Polynomial Approximation:

à Lagrange Polynomials

à Newton Polynomials

* They approximate: f(x) = a₀ + a₁x² + a₂x³ ……

à Padé Approximation

- They are approximations to functions using a quotient of 2 polynomials.

R_N,M(x) = (P_N(x))/(Q_M(x)) for a <= x <= b

(1) P_N(x) = P₀ + P₁x + P₂x² + … + P_Nx^N

(2) Q_M(x) = 1 + q₁x + q₂x² + … + q_Mx^M

*Padé Approximations are more precise than simple polynomial approximation with Newton and Lagrange polynomials.

- The polynomials P and Q are constructed so f(x) and R_N,M(x) agree at x = 0 and their derivatives also agree at x = 0

up to the N+M derivative.

- Assume the Maclaurin expansion (Maclaurin expansion = Taylor Expansion when x₀ = 0)

(3) f(x) = a₀ + a₁x + a₂x² + … + a_kx^k

- Assume that we want:

f(x) = R_N,M(x) = (P_N(x))/(Q_M(x))

f(x)Q_M(x) = P_N(x)

(4) f(x)Q_M(x) - P_N(x) = 0

* substitute (1), (2), and (3) into (4)

(a₀+a₁x+a₂x²+…+a_kx^k)(1+q₁x+q₂x²+…+q_mx^m) – (P₀+P₁x+P₂x²+…+P_nxⁿ) = 0

Factor x, x², x³,…:

(a₀-P₀) + x(a₁+a₀q₁-P₁) + x²(a₂+a₁q₁+a₀q₂-P₂) + … = 0

*To make the left side = 0 as well independently of the value of x, we need each coefficient to be 0

Therefore:

a₀-P₀ = 0

a₁+a₀q₁-P₁ = 0

a₂+a₁q₁+a₀q₂-P₂ = 0

…

Q_na_n+q_m-1a_n+1+…+a_n+m = 0

- Then we solve N+M+1 equations to obtain N+M+1 coefficients.

Example: Find the Padé Approximation R_2,2(x) for f(x) = (ln(1+x))/x

*Start with the Maclaurin 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) = (P₀ + P₁x + P₂x²) / (1 + q₁x + q₂x²)

- We want f(x) = R_2,2(x) à f(x) = P₂(x) / Q₂(x) à f(x)Q₂(x) – P₂(x) = 0

- Substitute for f(x), P₂(x), Q₂(x)

(1 – (x/2) + (x²/3) - (x³/4) + (x⁴/5))( 1 + q₁x + q₂x²) – (P₀ + P₁x + P₂x²) = 0

(1-P₀) + x((-1/2)+q₁-P₁) + x²((1/3)-(q₁/2)+q₂-P₂) + x³((1/5) – (q₁/4) + (q₂/3)) = 0 *Ignore other higher terms

1 – P₀ = 0 P₀ = 1

(-1/2) + q₁ – P₁ = 0 P₁ = q₁ – (1/2)

(1/3) – (q₁/2) + q₂ – P₂ = 0 P₂ = q₂ – (q₁/2) + (1/3)

(-q₂/2) + (q₁/3) – (1/4) = 0 (-3/4) + q₁ – (3/2)q₂ = 0

(q₂/3) + (q₁/4) + (1/5) = 0 + (4/5) – q₁ + (4/3)q₂ = 0

(-3/4) + (4/5) + ((3/2) + (4/3))q₂ = 0

q₂ = 3/10

q₁ = (3/2)q₂ + (3/4) q₁ = 6/5

P1 = q₁ – (1/2) = (6/5) – (1/2) P₁ = 7/10

P2 = q₂ – (q₁/2) + (1/3)

= (3/10) – ((6/5)/2) + (1/3) P₂ = 1/30

Therefore, we get:

f(x) = R_2,2(x) = (1 + (7/10)x + (1/3)x²) / (1 + (6/5)x + (3/10)x²)

Numeric Example:

f(1) = (ln(1+1))/1 = 0.6931

R_2,2(1) = 0.6933

- We can obtain ln(y) from f(x) = (ln(1+x))/x

(ln(1+x))/x = R_2,2(x) ln(1+x) = xR_2,2(x)

y = 1 + x

x = y -1

ln(y) = (y-1)R_2,2(y-1)

ln(y) = (y-1)((1 + (7/10)(y-1) + (1/3)(y-1)²) / (1 + (6/5)(y-1) + (3/10)(y-1)²))

Therefore, this expression can be used by the computer to approximate ln(y)

Using: 6 multiplications, 5 additions/subtractions, and 1 division

July 8^th , 2004

Midterm Review

- Floating Point Binary Representation

o Floating-Point

o Fixed-Point

o SPARC Floating-Point representation

- Propogation of Errors

o In Sums

o In Products

- Solution of Non-linear equations of the form f(x) = 0

o Fixed Point Theorem

o Types of convergence/divergence

§ Monotone convergence/divergence

§ Oscillating convergence/divergence

o Bisection Method (4)

o False Position Method (Regula-Falsi) (3)

o Newton-Rapson Method (2)

§ Similarities of N-R with Taylor Expansion

§ Numerical approximation of the derivative

§ Order of convergence

§ Examples of when N-R may not converge

o Secant Method

o Criteria for convergence

§ Horizontal convergence

§ Vertical convergence

o Well / Ill conditioned functions

- Solution of Linear Equations (Ax = B)

o Upper/Lower Triangular Systems

o Back Substitution

o Elementary Transformations to make upper triangular matrices

§ Scale

§ Swap

§ Addition of 2 rows

o Gaussian Elimination

§ Make A upper triangular O(n³)

§ Use Back Substitution O(n²)

o Pivoting / Choosing pivot

o LU Factorization (On³ + mO(n²)) for multiple systems of equations

o Gaussian Elimination vs. LU Factorization

- Iterative Methods for systems of Linear Equations

o When to use iterative methods

§ Large, sparse matrices

o Gauss-Seidel

o Jacobi

o Convergence in strictly diagonal matrices

- Interpolation and Polynomial Approximation

o Taylor Series

o Horner’s Method to optimally compute a polynomial

o Lagrange Polynomials

o Newton Polynomials

§ Divided Differences

o Padé Approximations using the ratio of 2 polynomials

Bring to Exam:

-Calculator

-1/2 page, one side formula sheet with anything you want (stapled to exam)

Study:

-Do homework #3 (Due Tuesday in class)

-Study the notes

-Solve previous midterm

-Send lecture notes (weeks 1-4)

-Solve Exercises in the book

Curve Fitting:

-Given a set of points come up with a curve that best fits the points

*The curve does not need to touch the points

Polynomial Approximation – passes through all the points

Curve Fitting – does not necessarily touch all the points, but passes close by them

-Example of when to use curve fitting:

-Assume you have an experiment that produces a set of points and

you would like to find the best line that fits the data points

Least Squares Line

-Assume we have recorded values (x₁,y₁), (x₂,y₂), …, (x_n,y_n)

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

-We have that for value (x_k,y_k) we have the error

f(x_k) = y_k + e_k where e_k is the error

-We would like to minimize the error for all points

-We can use several norms that tell us how far f(x) is from the data

Maximum Error à E_inf(f) = max[ f(x_k) 1<=k<=N-y_k]

n

Average Error à E₁(f) = (1/n)( Σ | f(x_k) – y_k | )

k=1

n

Root Mean Square Error à E₂(f) = ((1/n) Σ ( f(x_k) – y_k )²)^1/2

k=1

July 9^th , 2004

-We want to find the parameters of the function so the total error is minimized

-We choose to minimize the sum of the squares of the errors at each point (Root Mean Square Error)

-We want to find the parameters that minimize E₂(f)

Minimum Square Line

-Given the points (x₁,y₁), (x₂,y₂), …, (x_n,y_n), the least square line

y = f(x) = Ax + B is the line that minimizes the square error E₂(f)

n

E(A,B) = Σ (Ax + B - y_k)²

k=1

-To obtain the minimum we do the partial derivative of E(A,B) with respect to A and B

and make them equal to 0

-(1) and (2) give us a system of linear equations to solve A and B

-Solve A and B to find the line y = Ax + B that minimizes the error

Example:

-Assume the following points xk,yk. We want to obtain the line y = Ax + B that minimizes the error.

-We can apply minimum squares to other functions