Chen Guoyi

Submitted to DSA2102 Essential Data Analytics Tools: Numerical Computation Final Assignment

Abstract

Sample Document Constructed the Lagrange interpolating polynomial that interpolates \( f(x) = \cos(x) \) on the interval \([0, 2\pi]\) using 6 Chebyshev nodes. The coefficients of the polynomial are meticulously computed, followed by a graphical comparison with the original function to visually affirm the accuracy of the interpolation.

Introduction

Sample Document To solve the problem of finding the Lagrange interpolating polynomial for the function \( f(x) = \cos(x) \) on the interval \([0, 2\pi]\) using 6 Chebyshev nodes, we can follow these steps:

Identify Chebyshev Nodes: Chebyshev nodes are a set of optimal nodes for polynomial interpolation that minimize the interpolation error. For the interval \([0, 2\pi]\), the Chebyshev nodes can be calculated using the formula: \[ x_k = \frac{1}{2}\left[(b-a)\cos\left(\frac{2k-1}{2n}\pi\right) + a + b\right] \] where \(a = 0\), \(b = 2\pi\), \(n\) is the number of nodes, and \(k\) ranges from 1 to \(n\). In this case, \(n = 6\).

Calculate the Function Values at the Nodes: Evaluate the function \( f(x) = \cos(x) \) at each Chebyshev node to get the corresponding function values \( f(x_k) \).

Construct the Lagrange Basis Polynomials: For each node \( x_k \), we will construct a Lagrange basis polynomial \( L_k(x) \) which is defined as: \[ L_k(x) = \prod_{\substack{i=1 \\ i\neq k}}^{n} \frac{x – x_i}{x_k – x_i} \] where the product runs over all the nodes except \( x_k \).

Form the Lagrange Interpolating Polynomial: The interpolating polynomial \( P(x) \) is then the sum of the product of each function value and its corresponding Lagrange basis polynomial: \[ P(x) = \sum_{k=1}^{n} f(x_k) \cdot L_k(x) \]

Finally, we can round the coefficients and plot the polynomials for visual verification.

As a Computer Engineer, I will use C++ rather than R code to solve the Lagrange interpolating polynomial, then use MATLAB to plot the polynomial for verification.

Identification of Chebyshev Nodes

Sample Document Chebyshev nodes are a specific set of points in the domain of the function that are used to minimize the Runge’s phenomenon and to maximize the accuracy of the polynomial interpolation. These nodes are not uniformly spaced; instead, they are more densely clustered near the endpoints of the interval. The Chebyshev nodes for a given interval \([a, b]\) can be determined using the following formula:

\[ x_k = \frac{1}{2}\left[(b – a) \cos\left(\frac{2k – 1}{2n} \pi\right) + a + b\right], \quad k = 1, 2, \ldots, n \]
For our case, where the interval is \([0, 2\pi]\) and the number of nodes \(n\) is 6, the Chebyshev nodes can be calculated as follows:

\[ x_k = \pi \left[1 – \cos\left(\frac{2k – 1}{12} \pi\right)\right], \quad k = 1, 2, \ldots, 6 \]
These nodes are the x-values at which the function \(f(x)\) will be evaluated. The resulting values are then used in the construction of the Lagrange interpolating polynomial.

Hence, we may construct the code for calculation. See the output of Code Segment 1 in appendix A.1.

Calculation of the Function Values at the Nodes

Sample Document Once the Chebyshev nodes are identified, the next step is to evaluate the function \( f(x) = \cos(x) \) at these nodes. The function values at the nodes are essential for constructing the Lagrange interpolating polynomial. The values are obtained by simply applying the function to each of the Chebyshev nodes:

\[ f(x_k) = \cos(x_k), \quad k = 1, 2, \ldots, n \]
These values \( f(x_k) \) represent the y-coordinates of the function \( f(x) \) at the corresponding Chebyshev nodes \( x_k \). In the context of our problem, where \( n = 6 \), each \( x_k \) is substituted into the cosine function to yield six function values:

\[ f(x_1), f(x_2), f(x_3), f(x_4), f(x_5), f(x_6) \]
The resulting values are used in the Lagrange formula to construct the polynomial that passes through these specific points. Below is the code snippet that performs the evaluation of the cosine function at the Chebyshev nodes. See the output of Code Segment 2 in appendix A.2.

Construction of the Lagrange Basis Polynomials

Sample Document The Lagrange basis polynomials are fundamental components of the Lagrange interpolating polynomial. For each node \( x_k \), a basis polynomial \( L_k(x) \) is constructed such that \( L_k(x) \) is equal to 1 at \( x_k \) and 0 at all other nodes. The general form of the Lagrange basis polynomial is given by:

\[ L_k(x) = \prod_{\substack{i=1 \\ i \neq k}}^{n} \frac{x – x_i}{x_k – x_i} \]
where \( n \) is the total number of nodes, and \( x_i \) represents each of the Chebyshev nodes except \( x_k \). The product runs over all nodes except for the node at which the polynomial is centered, \( x_k \). This ensures that each \( L_k(x) \) has roots at every node except \( x_k \).

In practice, each \( L_k(x) \) is a polynomial of degree \( n-1 \) and when evaluated at the node \( x_k \), all terms in the product except for the \( k \)-th term are zero, resulting in \( L_k(x_k) = 1 \). Conversely, when \( L_k(x) \) is evaluated at any other node \( x_j \), where \( j \neq k \), the \( j \)-th term in the product will be zero, thus ensuring \( L_k(x_j) = 0 \).

The construction of these polynomials is critical as they form the basis of the interpolation, where each polynomial will be scaled by the function value at its respective node.

Here is the code to construct the Lagrange basis polynomials. See the output of Code Segment 3 in A.3.

Formation of the Lagrange Interpolating Polynomial

Sample Document The final step in constructing the Lagrange interpolating polynomial is to combine the Lagrange basis polynomials with the corresponding function values. The interpolating polynomial \( P(x) \) is formed as a weighted sum of the basis polynomials, where the weights are the function values at the Chebyshev nodes. Mathematically, the interpolating polynomial is expressed as:

\[ P(x) = \sum_{k=1}^{n} f(x_k) \cdot L_k(x) \]
where \( f(x_k) \) is the function value at the \( k \)-th Chebyshev node, and \( L_k(x) \) is the corresponding Lagrange basis polynomial. The polynomial \( P(x) \) will agree with \( f(x) \) at each Chebyshev node, thus interpolating the function at those points.

The following C++ code snippet demonstrates how to form the Lagrange interpolating polynomial by summing up the products of the function values and the Lagrange basis polynomials. See the output of Code Segment 4 in appendix A.4.

Sample Document In this code, scalePolynomial is used to multiply a Lagrange basis polynomial by its corresponding function value at a Chebyshev node, effectively scaling the polynomial. The function addPolynomials then adds the resulting polynomials together to form the full interpolating polynomial. This polynomial can then be used to estimate the function \( f(x) \) at any point within the interval.

Visual Verification

Sample Document The final step in the verification of our interpolating polynomial is to visually compare the graph of \( P(x) \), our Lagrange interpolating polynomial, with the graph of the original function \( f(x) = \cos(x) \). By plotting both functions over the interval \([0, 2\pi]\), we can observe how closely \( P(x) \) approximates \( f(x) \). This visual comparison serves as a heuristic check on the accuracy of our interpolation.

Sample Document This code snippet generates a plot of both \( f(x) \) and \( P(x) \), with the Chebyshev nodes highlighted. The cosine function is plotted as a solid blue line, while the interpolating polynomial is plotted as a red dashed line, allowing for clear visual distinction. The black circles indicate the Chebyshev nodes, where the polynomial should intersect with the cosine function.

Appendix A: Output

A.1 Output of Code Segment 1

A.2 Output of Code Segment 2

A.3 Output of Code Segment 3

A.4 Output of Code Segment 4

Appendix B: Source Code

Please download the code from my GitHub Repository. (Link Not Available Now)

Acknowledgment

As the DSA2102 course draws to a close, I reflect on my learning journey through the last page of this final assignment, extending my special thanks to the professors and friends who have guided and supported me. Their advice and encouragement have been crucial to my growth, particularly the inspirational teaching of Prof Timothy Wertz, who helped me understand the theory and ignited my passion for applying knowledge in practice.

As mentioned in the introduction of my paper, my major is Computer Engineering, and I chose Data Science and Analytics as my second major at the beginning of this semester. DSA2102 is not my first course in my second major, but it holds a special significance in my academic career. As an NUS student on exchange at the University of California, Los Angeles, the courses I studied there in Probability Theory and Regression Analysis closely related to the matrix operations in DSA2102, deepening my understanding of these concepts and their application.

As an engineer, I aim to apply the knowledge I learned at university to solve real-world problems. During my studies, I was particularly captivated by Prof Wertz’s example of his grayscale cat image compression to explain the SVD algorithm. Because I am about to undertake the Undergraduate Research Opportunity Program (UROP) at the NUS Advanced Robotics Centre, focusing on computer vision, so I tried to improve the professor’s algorithm and achieved SVD compression of color images. I obtained a compressed color image by applying SVD separately to each color channel (red, green, and blue) and then recombining them. In the future, I plan to explore how to compress and reassemble more dimensional information, such as depth and infrared information of a picture. This not only demonstrates my ability to transform theoretical knowledge into practical application but also paves the way for my future research in the field of robotics.

Choosing Data Science and Analytics as my second major enhanced my sensitivity and capability in handling data, supporting my exploration of machine learning. I am grateful to Professor Wertz and the teaching assistant team of DSA2102 for their meticulous instruction. I take pride in the knowledge I have acquired in DSA2102 and look forward to applying this valuable knowledge in future projects and research.

Finally, I would like to thank my friends, with whom I sat in the front row in LT32 every Tuesday and Friday to listen to the nice lectures and took the D2 Shuttle Bus back to UTown for dinner together. These actions align with the most emphasized phrase in the professor’s slides:

“Prioritize your well-being.”

Print Page