Theory of Approximation in Interpolation Techniques
Explore the theory of approximation in interpolation presented by Abhas Singh from the Department of Civil Engineering at IIT Kanpur. Learn about discrete data observations, interpolation polynomials like Newton's Divided Difference and Lagrange Polynomials, and the application of Spline Interpolation for smoothing functions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Theory of Approximation: Interpolation Abhas Singh Department of Civil Engineering IIT Kanpur Acknowledgements: Profs. Saumyen Guha and Shivam Tripathi (CE)
Discrete Data (n + 1) observations or data pairs [(x0, y0), (x1, y1), (x2, y2) (xn, yn)] (m + 1) basis functions: ?0,?1,?2, ?? Approximating polynomial: ? ? = ?=0 ?0?0?0 + ?1?1?0 + ?2?2?0 + + ?????0 = ?0 ?0?0?1 + ?1?1?1 + ?2?2?1 + + ?????1 = ?1 :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: ?0?0?? + ?1?1?? + ?2?2?? + + ?????? = ?? n equations, m unknowns: m < n: over-determined system, least square regression m = n: unique solution, interpolation m > n: under-determined system ? ?????
Interpolation Polynomials Newton s Divided Difference Lagrange Polynomials Gram s polynomials (introduced earlier) Spline Interpolation: piecewise continuous, smoothing
Newtons Divided Difference For a net of points ?0,?1,?2, ??, formulate a triangular set of basis polynomials ?0? = 1 ?1? = ? ?0 ?2? = ? ?0 ? ?1 ?3? = ? ?0 ? ?1 ? ?2 ??? = ? ?0 ? ?1 ? ?? 1 ??? = ? ?0 ? ?1 ? ?? 1
Newtons Divided Difference Consider a net of points ?0,?1,?2, ?? and the corresponding function values as ?0,?1,?2, ?? Newton s polynomial is: ? ? = ?0+ ?1? ?0 + ?2? ?0 ? ?1 +?3? ?0 ? ?1 ? ?2 +??? ?0 ? ?1 ? ?? 1 True function: ? ? = ? ? +??+1? ? + 1 !? ?0 ? ?1 ? ?? for some? int ?,?0,?1 ??
Newtons Divided Difference Newton s polynomial with the remainder term: ? ? = ?0+ ?1? ?0 + ?2? ?0 ? ?1 +?3? ?0 ? ?1 ? ?2 +??? ?0 ? ?1 ? ?? 1 +? ? ? ?0 ? ?1 ? ?? ? ?0 = ?0= ?0; Taking f0 on the LHS and dividing by ? ?0 ? ?0,? =? ? ? ?0 = ?1+ ?2? ?1 ? ?0 + ?3? ?1 ? ?2 + ??? ?1 ? ?? 1 + ? ? ? ?1 ? ?? ? ?0,?1 =?1 ?0 = ?1 ?1 ?0
Newtons Divided Difference ? ?0,? =? ? ? ?0 = ?1+ ?2? ?1 ? ?0 + ?3? ?1 ? ?2 + ??? ?1 ? ?? 1 + ? ? ? ?1 ? ?? Taking ? ?0,?1 on the LHS and dividing by ? ?1: ? ?0,?1,? =? ?0,? ? ?0,?1 = ?2+ ?3? ?2 + ? ?1 +??? ?2 ? ?? 1 + ? ? ? ?2 ? ?? ? ?0,?1,?2 =? ?0,?2 ? ?0,?1 = ?2 ?2 ?1
Newtons Divided Difference ? ?0,?1,? =? ?0,? ? ?0,?1 = ?2+ ?3? ?2 + ? ?1 +??? ?2 ? ?? 1 + ? ? ? ?2 ? ?? Taking ? ?0,?1,?2 on the LHS and dividing by ? ?2: ? ?0,?1,?2,? =? ?0,?1,? ? ?0,?1,?2 = ?3+ ?4? ?3 + ? ?2 + ??? ?3 ? ?? 1 + ? ? ? ?3 ? ?? ? ?0,?1,?2,?3 =? ?0,?1,?3 ? ?0,?1,?2 = ?3 ?3 ?2
Newtons Divided Difference ? ?0,?1, ?? 1,? =? ?0,?1, ?? 2,? ? ?0,?1, ?? 2,?? 1 ??+1? ?? + + ??? ?? ? ?? 1 + ? ? ? ?? ? ?? = ??+ ? ?? 1 ? ?0,?1,?2, ?? =? ?0,?1, ?? 2,?? ? ?0,?1, ?? 2,?? 1 = ?? ?? ?? 1 ? ?0,?1,?2, ?? = ??; ? ?0,?1,?2, ??,? = ? ? Newton s polynomial without the remainder term: ? ? ? = ?0+ ? ?0,?1, ?? ? ?0 ? ?1 ? ?? 1 ?=1
Recall: Properties of Divided Differences 1st Divided Difference: ? ??,?? 1 =?? ?? 1 =?? 1 ?? ?? 1 ?? = ? ?? 1,?? ?? ?? 1 2nd Divided Difference: ? ??,?? 1,?? 2 =? ??,?? 1 ? ?? 1,?? 2 ?? ?? 2 =? ??,?? 1 ? ??,?? 2 ?? 1 ?? 2 =? ??,?? 2 ? ?? 1,?? 2 ?? ?? 1 ? ??,?? 1,?? 2 = ? ?? 1,??,?? 2 = ? ?? 2,?? 1,?? = ? ??,?? 2,?? 1
Properties of Divided Differences 2nd Divided Difference: ? ??,?? 1,?? 2 =? ??,?? 1 ? ?? 1,?? 2 ?? ?? 2 ? =? ??,?? 1 ? ??,?? 2 ?? 1 ?? 2 ?? ?? 1 ?? ?? 1 ?? ?? 2 ?? 1 ?? 2 ?? ?? 2 = +?? 1?? 1 ?? 1?? 1 =???? ???? 1 ?? 2??+ ?? 2?? 1 ????+ ???? 2+ ?? 1?? ?? 1?? 2 ?? ?? 1 ?? 1 ?? 2 ?? ?? 2 ?? 1 ?? 2?? ?? 1 ?? 2?? 1 ?? ?? 1?? 1+ ?? ?? 1?? 2 ?? ?? 1 ?? 1 ?? 2 ?? ?? 2 ?? ?? 1 ?? ?? 1 ?? 1 ?? 2 ?? 1 ?? 2 ?? ?? 2 ?? ?? 2 = =? ??,?? 1 ? ?? 1,?? 2 = = ? ??,?? 1,?? 2
Newtons Divided Difference Recursion Formula for Divided Difference: (Recall: discussion during Muller s method) The order of the points within the divided difference is immaterial. To see it generally, consider this: ? ?0,?1, ??,? =? ?0,?1, ?? 1,? ? ?0,?1, ?? 1,?? ? ?? For generalization: replace the index zero with (i + 1) evaluate the divided difference at x = xi ? ??+1,??+2, ??,?? =? ??+1,??+2, ?? 1,?? ? ??+1,??+2, ?? 1,?? ?? ?? ? ??,??+1, ?? =? ??,??+1, ?? 1 ? ??+1, ?? 1,?? ?? ??
Newtons Divided Difference ? ??,??+1, ?? =? ??,??+1, ?? 1 ? ??+1, ?? 1,?? ?? ?? =? ??+1, ?? 1,?? ? ??,??+1, ?? 1 ?? ?? Or by reversing the order of x variables, ? ??,?? 1, ?? =? ?? 1, ??+1,?? ? ??,?? 1, ??+1 ?? ?? =? ??,?? 1, ??+1 ? ?? 1, ??+1,?? ?? ??
Newtons Divided Difference Examples: ? ??,?? 1, ?? =? ??,?? 1, ??+1 ? ?? 1, ??+1,?? ?? ?? ? = 1,? = 0:? ?1,?0 =? ?1 ? ?0 ?1 ?0 ? = 2,? = 1:? ?2,?1 =? ?2 ? ?1 ?2 ?1 ? = 2,? = 0:? ?2,?1,?0 =? ?2,?1 ? ?1,?0 ?2 ?0 ? = 3,? = 1:? ?3,?2,?1 =? ?3,?2 ? ?2,?1 ?3 ?1 ? = 3,? = 0:? ?3,?2,?1,?0 =? ?3,?2,?1 ? ?2,?1,?0 ?3 ?0
Newtons Divided Difference:Example x0 , f(x0) f[x1, x0] f[x2, x1, x0] f[x3, x2, x1, x0] f[x2, x1] f[x3, x2, x1] x1 , f(x1) x2 , f(x2) f[x3, x2] x3 , f(x3) p(x) = f(x0) + f[x1, x0](x - x0) + f[x2, x1, x0](x - x0)(x x1) + f[x3, x2, x1, x0](x - x0)(x x1)(x x2)
Newtons Divided Difference: Example 1 , -48 2 9 2 29 17 2 , -46 4, 12 80 5 , 92 ? ? = 48 + 2 ? 1 + 9 ? 1 ? 2 + 2 ? 1 ? 2 ? 4 = 2?3 5?2+ 3? 48 p(x) = f(x0) + f[x1, x0](x - x0) + f[x2, x1, x0](x - x0)(x x1) + f[x3, x2, x1, x0](x - x0)(x x1)(x x2)
Newtons Divided Difference: Error Estimate Newton s Divided Difference: Error Estimate Recall the Newton s polynomial with the remainder: ? ? = ? ? +??+1? ? + 1 !? ?0 ? ?1 ? ?? for some? int ?,?0,?1 ?? ? ? = ? ? + ? ? ? ?0 ? ?1 ? ?? We derived: ? ?0,?1,?2, ??,? = ? ? If an extra-data {xn+1, f(xn+1)} is available, it is possible to make an approximate estimate of the error as: ? ?0,?1,?2, ??,??+1 = ? ??+1 ? ?and the error (E) as: ? ? ?0,?1,?2, ??,??+1 ? ?0 ? ?1 ? ??
Newtons Divided Difference ? ?0,?1, ?? 1,? =? ?0,?1, ?? 2,? ? ?0,?1, ?? 2,?? 1 ??+1? ?? + + ??? ?? ? ?? 1 + ? ? ? ?? ? ?? = ??+ ? ?? 1 ? ?0,?1,?2, ?? =? ?0,?1, ?? 2,?? ? ?0,?1, ?? 2,?? 1 = ?? ?? ?? 1 ? ?0,?1,?2, ?? = ??; ? ?0,?1,?2, ??,? = ? ? Newton s polynomial without the remainder term: ? ? ? = ?0+ ? ?0,?1, ?? ? ?0 ? ?1 ? ?? 1 ?=1
Lagrange Polynomials Unit linear polynomials for two nodes: ?0,?1 ? ?1 ?0 ?1; ?1? =? ?0 ?0? = ?1 ?0 Unit quadratic for three nodes: ?0,?1,?2 ? ?1 ? ?2 ?0 ?1 ?0 ?2 ? ?0 ? ?2 ?1 ?0 ?1 ?2 ?0? = ; ?1? = ? ?0 ? ?1 ?2 ?0 ?2 ?1 ?2? = Polynomials of order n for the mesh of nodes ?0,?1,?2, ?? ? ? ?? ?? ?? ???? = 0 ??? ? ? 1 ??? ? = ? ??? = ?=0 ? ?
Lagrange Polynomials Polynomials to be fitted to a mesh of nodes ?0,?1,?2, ?? and the corresponding function values as ?0,?1,?2, ?? Lagrange polynomial is: ? ? ? ?? ?? ?? ? ? = ????? ??? = ?=0 ? ? ?=0
Lagrange Polynomials Polynomials to be fitted to a mesh of nodes ?0,?1,?2, ?? and the corresponding function values as ?0,?1,?2, ?? Lagrange polynomial is: ? ? ? ?? ?? ?? ? ? = ????? ??? = ?=0 ? ? ?=0
Lagrange Polynomial: Example Write the cubic polynomial using Lagrange polynomials that passes through the following four points: (1 , -48), (2 , -46), (4, 12), (5 , 92)? ? ? ? 2 ? 4 ? 5 1 2 1 4 1 5 ? 1 ? 2 ? 5 4 1 4 2 4 5 5 1 5 2 5 4 = 4 ? 2 ? 4 ? 5 23 3 +23 3 Recall Newton s polynomial through the same set of points: ? ? = 48 + 2 ? 1 + 9 ? 1 ? 2 + 2 ? 1 ? 2 ? 4 = 2?3 5?2+ 3? 48 ? 1 ? 4 ? 5 2 1 2 4 2 5 ? 1 ? 2 ? 4 = 48 + 46 + 12 + 92 ? 1 ? 4 ? 5 2 ? 1 ? 2 ? 5 ? 1 ? 2 ? 4 = 2?3 5?2+ 3? 48
Example Fit Fit an interpolation polynomial through the following four points: (1 , -48), (2 , -46), (4, 12), (5 , 92) ? ? = 2?3 5?2+ 3? 48
