July 14, 2003

 

Midterm Topics:

I.                   Representation of Floating Point Numbers

a.      Mantissa and Exponent

b.      Fixed Point Numbers

c.      SPARC Representation

II.                 Propagation Errors

III.              Solution of Nonlinear Equations

a.      Fixed point of an equation

b.      Fixed point theorem

c.      Convergence and Divergence

                                                              i.      Monotone convergence/divergence

                                                             ii.      Oscillating convergence/divergence

d.      Iteration Methods

                                                              i.      Bisection Method

                                                             ii.      False Position Method (Regula Falsi)

1.      Horizontal Convergence ( |yk | < ε )

2.      Vertical Convergence ( | xk – xk-1 | < ε )

                                                           iii.      Newton Raphson Method

1.      Understand the similarities and differences between Newton Raphson and Taylor Expansion

2.      Numerical Approximation of the derivative of a function

3.      Know the limits of the Newton Raphson Method

4.      Understand the Order of Convergence

                                                          iv.      Secant Method

IV.               Solution of Linear Systems Ax = B

a.      Properties of Vectors

b.      Vector Algebra

c.      Matrices / Properties of Matrices

d.      Zero / Identity Matrix

e.      Inverse of a Matrix

f.       Determinants

g.      Upper Triangular Systems and Solution using back substitution

h.      Elementary Matrix Transformations

i.        Gauss Elimination (pivoting)

j.        LU Factorization (Triangular factorization) – forward and back substitution

k.      Know when to use both Gauss elimination and LU factorization

l.        Iterative methods for linear equations

                                                              i.      Jacobi

                                                             ii.      Gauss – Seidel

m.    Iterpolation and Polynomial Approximation

 

Study Materials

I.                   Notes

II.                 The Book

III.              Homework 2 and 3

IV.               Floating Point Representation of Homework 1

 

The exam will be on Thursday, from 7-9 p.m. in BRNG (formally LAEB) 2280.  You may bring a ½ page formulary and a calculator.

 

 

July 15, 2003

 

I.                   Curve Fitting

a.      Suppose we have (x1, y1) … (xn, yn) and we want to create an exponential curve to fit these points.

b.      f(x) = y = CeAx - A and c must be obtained in order to properly fit the data points

c.      To accomplish this we may use the least-squares procedure

                                                              i.      E(C, A) = Σk=1n (f(xk) – y)2 = Σk=1n (CeAx – y)2

                                                             ii.      ğE / ğC = Σk=1n 2(CeAxk – y)eAxk

                                                           iii.      2 Σk=1n (Ce2Axk – eAxkyk) = 0

                                                          iv.      1.  C Σk=1n(eAxk) = Σk=1n(eAxkyk)

                                                            v.      ğE / ğC = Σk=1n 2(CeAxk – y)CxkeAxk = 0

                                                          vi.      Σk=1n (C2xke2Axk - ykCxkeAxk) = 0

                                                         vii.      2. C2 Σk=1n(xke2Axk) - C Σk=1n(ykxkeAxk) = 0

d.      NOTE: Lines marked with orange gives a system of two non-linear equations that can be solved using the Newton Method.

                                                              i.      The method will give an accurate result for reducing the least-square error. 

                                                             ii.      It is possible to get a less accurate result using a linearization method

II.                 Transformations Using Data Linearization

a.      It is possible to reduce the problem of fitting data into curves by transforming these types of equations into linear equations.

b.      The constants can then be obtained by using the least squares for a line.

c.      EXAMPLE:

                                                              i.      Imagine that we want to fit data into the curve y = CeAx

                                                             ii.      ln y = ln(CeAx)

                                                           iii.      ln y = ln C + ln(eAx)

                                                          iv.      ln y = ln C + Ax

                                                            v.      Z = ln y, B = ln C, thus

                                                          vi.      Z = Ax + B

                                                         vii.      Then we can try and fit the data into the linearized function and obtain A and B.

d.      EXAMPLE:

                                                              i.      Assume:

Xk

 

Yk

0

 

1.5

1

 

2.5

2

 

3.5

3

 

5.0

4

 

7.5

                                                             ii.      We want to fit this data into the curve y = CeAx

1.      ln y = ln C + Ax

2.      Z = AX + B

                                                           iii.      Find the least squares function for Z = Ax + B

Xk

Yk

Zk = ln(yk)

Xk2

XkZk

0

1.5

.4055

0

0

1

2.5

.9163

1

.9163

2

3.5

1.2528

4

2.5056

3

5.0

1.6094

9

4.8282

4

7.5

2.0149

16

8.0596

10

 

6.1989

30

16.3097

                                                          iv.      Least Squares Line Solution

1.      0 = A Σk=1n(xk2) + B Σk=1n(xk) - Σk=1n(xkzk)

2.      0 = A Σk=1n(xk) + BN - Σk=1n(zk)

                                                            v.      Then you plug the derived values into the equation and get

1.      0 = A(30) + B(10) – 16.3097

2.      0 = A(10) + B(5) – 6.1989

                                                          vi.      Then we solve for B

1.      B = (16.3097 – A(30)) / 10 = (16.3097 - .3912(30)) / 10 = .4574

                                                         vii.      We know that B = ln C

1.      C = eB = e.4574 = 1.579

                                                       viii.      Thus, the equation that best fits the data is: y = 1.579e.3912x

                                                           ix.      You can use the following substitutions to linearize an equation. There are more in the book

1.      y = A/x + B   -> Z = 1/x  AND y = AZ + B

2.      y = ACx  ->  Z = ln x

3.      ln y = ln(CxA) -> W = ln y

4.      ln y = ln C + A ln x -> B = ln c  AND W = AZ + B

 

 

July 16, 2003

 

I.                   Linear Least Squares

a.      Imagine that you have N data points (x1, y1), …, (xN, yN) and you want to fit these points to the sum of M independent functions:

                                                              i.      f(x) = c1f1(x) + c2f2(x) + … + cMfM(x)

b.      We want c1, c2, …, cM to minimize the square error to approximate (x1, y1), …, (xN, yN)

                                                              i.      E(c1, c2, …, cM) = Σk=1n (f(xk) – yk)2 = Σk=1n (c1f1(xk) + c2f2(xk) + …+ cMfM(xk) – y k) 2 = Sk=1NSj=1M(c jf j(xk) – yk) 2

                                                             ii.      ğE/ğci = Σk=1n 2* Σj=1M(cjfj(xK) - yk) * (fi(xk)) = 0

                                                           iii.      Σk=1n Σj=1M(cjfj(xK) fi(xK)) - Σk=1n(yk fi(xK)) = 0   for i = 1, …, M

c.      This gives us M linear equations so that we can solve c1, c2, …, cM (M variables)

d.      When we solve this system, we get the best c1, c2, …, cM to fit (x1, y1), …, (xN, yN)

                                                              i.      f(x) = c1f1(x) + c2f2(x) + … + cMfM(x)

II.                 Polynomial Fitting – Specific Case of Linear Least Squares

a.      Given a set of data points (x1, y1), …, (xN, yN), we wish to find the c1, c2, …, cM+1 in the function: f(x) = c1+ c2x + c3x2 + …+ cM+1xM, that best fits the data:

                                                              i.      f1(x) = 1

                                                             ii.      f2(x) = x

                                                           iii.      f3(x) = x2

                                                          iv.      etc.

b.      Example:

c.       We want to find A, B, C for: f(x) = Ax2 + Bx + C that best fits (x1, y1), …, (xN, yN), minimizing the square error

                                                              i.      E(A,B,C) = Sk=1N (Ax k 2 + Bx k + C – y k) 2

                                                             ii.      ğE/ğA = Σk=1n 2 * (Axk2 + Bx k + C – y k) * xk2 = 0

                                                           iii.      1. AΣk=1N xk4 + BΣk=1N xk3 + CΣk=1N xk2 = Σk=1N xk2 yk

                                                          iv.      ğE/ğB = Σk=1n 2 * (Axk2 + Bx k + C – y k) * xk = 0

                                                            v.      2. ASk=1N xk3 + BSk=1N xk2 + CSk=1N xk = Sk=1N xk yk

                                                          vi.      ğE/ğC = Σk=1n 2 * (Axk2 + Bx k + C – y k) = 0

                                                         vii.      3. ASk=1N xk2 + BSk=1N xk + CN = Sk=1N yk

d.      Equations 1, 2, and 3 form a system of 3 linear equations of 3 variables that will give the best A, B, and C to fit the function: f(x) = Ax2 + Bx + C

e.      When using high degree polynomials, there is a problem.  The higher the degree of the polynomial, the more maximum and minimum points it will have.  Thus the curve will wiggle.  In order to avoid the problem of curve wiggle, we use spline functions.

III.              Interpolation by Spline Functions

a.      Splines are a set of curves that fit a set of points piecewise.  Instead of having a single polynomial to fit all of the points, we have multiple polynomials connected to one another.

b.       

c.     

d.      S1(x) and S2(x) are continuous in y but they are not continuous in y’

                                                              i.      S1(x2) = S2(x2)

                                                             ii.      S1’(x2) ~= S2’(x2)

e.      The simplest spline is one that uses a polynomial of degree 1. Such as the following

f.      

g.      S1(x) = y0 + ((y1 – y0) / (x1 – x0)) * (x - x0) when x0 <= x <= x1

h.      S2(x) = y1 + ((y2 - y1) / (x2 – x1)) * (x – x1) when x1 <= x <= x2

i.        etc.

j.        We could use the same approach with quadratic splines.  In that case, for every 3 points, we will use a different spline.  But, when we have 1 spline that is connected to the next one, there will be a dramatic change in the deviation.

IV.               Piecewise Cubic Splines

a.      To have continuity also in the first and second derivatives, we use points before and after the interval of the spline.

b.     

c.      Cubic splines are the most common because they can be built to satisfy the following properties

                                                              i.      S(xk) = yk  (Guarantees that the splines pass through the data points)

                                                             ii.      Sk(xk+1) = Sk+1(xk+1) (Continuous in y)

                                                           iii.      Sk’(xk+1) = Sk+1’(xk+1) (Continuity in the first derivative)

                                                          iv.      Sk’’(xk+1) = Sk+1’’(xk+1) (Continuity in the second derivative)

 

 

July 17, 2003

 

I.                   Piecewise Cubic Splines

a.      The goal is to fit N+1 data points (x0, y0), …, (xN, yN), where a = x0 < x1 < … < xn = b, into N cubic polynomials Sk(x) with coeffiecients Sk,0, Sk,1, Sk,2 and Sk,3

b.     

c.      We want Sk(x) k = 0, …, N-1 to satisfy

                                                              i.      S(x) = Sk(x) = Sk,0 + Sk,1(x-xk) + Sk,2(x-xk)2 + Sk,3(x-xk)3 for xk <= x <= xk+1 and k = 0, 1, …, N-1.  We will use a different cubic polynomial between each consecutive pair of points.

                                                             ii.      S(xk) = yk  for k = 0, 1, …, N (Spline passes through all data points)

                                                           iii.      Sk(xk+1) = Sk+1(xk+1) for k = 0, 1, …, N-2.  (The end of a spline touches the beginning of the next spline

                                                          iv.      Sk’(xk+1) = Sk+1’(xk+1) for k = 0, 1, …, N-2 (Continuity in the first derivative at the point of contact between 2 splines)

                                                            v.      Sk’’(xk+1) = Sk+1’’(xk+1) for k = 0, 1, ..., N-2 (Continuity in the second derivative at the point of contact between two splines.

d.      For each polynomial Sk(x) there are four coefficients that need to be determined

e.       Sk,0, Sk,1, Sk,2 and Sk,3 (the 4 degrees of freedom)

f.       Also, we have N splines S0(x), S1(x), …, SN(x)

g.      Therefore there are 4N coefficients to be determined.  How do we get these coefficients?

                                                              i.      We need 4N equations that have to come from 4N constraints. 

                                                             ii.      From II and with N+1 data points = N+1 equations

                                                           iii.      From III, IV, and V each supplies N-1 equations = 3(N-1)

                                                          iv.      N + 1 + 3(N-1) = 4N – 2 equations

                                                            v.      There are 2 equations missing to have the problem fully constrained.  This gives us two degrees of freedom that will involve S’(x) and S’’(x) at x0 and xN.  The will be discussed later.

                                                          vi.      Since Sk(x) is cubic, the second derivative is a line.  We can obtain the equation of this line using Lagrange approximation.

1.      S’’k(x) = S’’(xk)(x – xk+1) / (xk – xk+1) + S’’(xk+1)(x – xk)(x - xk) / (xk+1 - xk)

2.      So S’’k(x) = S’’(xk) when x = xk and S’’k(x) = S’’(xk+1) when x = xk+1

3.      Assume that we create constants:

a.      mk = S’’(xk)

b.      mk+1 = S’’(xk+1)

c.      hk = xk+1 - xk

4.      S’’k(x) = mk(x - xk+1) / -hk + mk+1(x - xk) / hk = mk(xk+1 – x) / hk + mk+1(x - xk) / hk

5.      To obtain Sk(x) we need to integrate twice.

a.      Sk(x) = òò S’’(x) dx dx = òò mk(xk+1 – x) / hk + mk+1(x – xk) / hk dx dx

b.      = ò -.5(mk / hk) (xk+1 – x)2 + .5(mk+1 / hk)( x - xk)2 + C1 dx

c.      = .5(1/3)( mk / hk)( xk+1 – x)3 + .5(1/3)( mk+1 / hk)(x - xk)3 + C1x + C2 (We express C1x + C2 = pk(xk+1 – x) + qk(x - xk))

d.      = (mk / 6hk)( xk+1 – x)3 + (mk / 6hk)( x - xk)3 + pk(xk+1 – x) + qk(x - xk)

e.      Then you substitute in xk, xk+1 and S(xk) = yk and S(xk+1) = y

                                                                                                                                      i.      Sk(xk) = yk = (mk / 6 hk)( xk+1 - xk) 3 + (mk+1 / 6 hk)( x - xk) 3 + pk(xk+1 – x) + qk(x - xk)

                                                                                                                                     ii.      Yk = (mk / 6hk)(hk)3 + pk(hk) = (1/6)( mkhk2) + pkhk

                                                                                                                                   iii.      Sk(xk+1) = yk+1 = (mk / 6hk)(hk)3 + qkhk = (1/6)( mk+1hk2) + qkhk

                                                                                                                                  iv.      1. Yk = (1/6)( mkhk2) + pkhk

                                                                                                                                    v.      2. Yk+1 = (1/6)( mk+1hk2) + qkhk

                                                                                                                                  vi.      We can then use (1) to retrieve pk

1.      pk = (yk - mkhk2/6)(1/hk) = (yk / hk - mkhk/6)

                                                                                                                                 vii.      We can the use (2) to retrieve qk

1.      qk = (yk+1 - mk+1 hk2/6)(1 / hk) = (yk+1 / hk - mk+1 hk/6)

                                                                                                                               viii.      Then we can substitute (1) and (2) into

1.      Sk(x) = (mk / 6 hk)( xk+1 - x)3 + (mk+1 / 6 hk)( x - xk)3 + pk(xk+1 – x) + qk(x - xk)

2.      Sk(x) = (mk / 6 hk)( xk+1 - x)3 + (mk+1 / 6 hk)( x - xk)3 + (yk / hk - mkhk/6) (x - xk)

                                                                                                                                   ix.      The only terms left to find are mk and mK+1