数值计算笔记之插值(一）拉格朗日插值

0、插值的概念

简单来讲插值就是定义一个在特定点取给定值的函数的过程。

1、解决的问题

已知函数在某些点上的函数值，要求得一个函数使其通过这些点，或进一步确定在其他点的函数值。即由给定的几个初始点，能够把其余的点求出来，从而拟合成一条光滑的曲线。

2、插值的定义：

设 $y = f(x)$ 在 $[a,b]$ 上有定义， $x_{0},x_{1},\cdots ,x_{n}$ 是 $[a,b]$ 上的 $n+1$ 个互异点，且 $f(x)$ 在这些点上的函数值为 $y_{0},y_{1},\cdots ,y_{n}$ 。若存在 $\varphi (x)$ ，使 $\varphi (x_{i} )= y_{i}(i = 0, 1, \cdots ,n)$ ，则称 $\varphi (x)$ 为 $f(x)$ 的插值函数。

这时有人就懵了，既然知道 $f(x)$ ，那为什么还要求 $\varphi (x)$ ，这不是多此一举吗？原因如下：

可能我们不知道 $f(x)$ ，只知道它上面的一些点，这时需要来估计 $\varphi (x)$ ；
$f(x)$ 本身太复杂，希望找到一个更方便计算的函数 $\varphi (x)$ 。

$f(x)$ 称为被插值函数， $\varphi (x)$ 称为插值函数
$[a,b]$ 称为插值区间
$\varphi (x_{i} )= y_{i}(i = 0, 1, \cdots ,n)$ 称为插值条件
求 $\varphi (x)$ 的方法称为插值法

一、拉格朗日插值法

1、定理：

当插值节点互异时，且节点数目为 $n+1$ ，则满足插值条件的 $n$ 次插值多项式存在且唯一。

即有 $\varphi (x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}$

2、线性插值（n=1)

已知插值节点为 $x_{0},x_{1}$ ，且 $f(x)$ 在其上的函数值为 $y_{0},y_{1}$ 。求 $L_{1}(x)$ ，使 $L_{1}(x_{0}) = y_{0},L_{1}(x_{1})=y_{1}$ .

$\therefore L_{1}(x)$ 为过 $(x_{0},y_{0}),(x_{1},y_{1})$ 的直线

$L_{1}(x) = \frac{x-x_{1}}{x_{0}-x_{1}}y_{0}+\frac{x-x_{0}}{x_{1}-x_{0}}y_{1}$ ，这很容易的出来，详细过程不多说了。

将 $\frac{x-x_{1}}{x_{0}-x_{1}}$ 记为 $l_{0}(x)$ ， $\frac{x-x_{0}}{x_{1}-x_{0}}$ 记为 $l_{1}(x)$ ，则有

$\left\{\begin{matrix} l_{0}(x_{0}) = 1, &l_{0}(x_{1}) = 0 \\ l_{1}(x_{0})=0, &l_{1}(x_{1})=1 \end{matrix}\right.$ 称 $l_{0}(x)$ ， $l_{1}(x)$ 为基函数。

3、抛物线插值（n=2)

$x$	$x_{0}$	$x_{1}$	$x_{2}$
$f(x)$	$y_{0}$	$y_{1}$	$y_{2}$

求 $L_{2}(x)$ ，使 $L_{2}(x_{i}) = y_{i} (i=0,1,2,\cdots )$ 。那么

设 $L_{2}(x) = l_{0}(x)\cdot y_{0} + l_{1}(x)\cdot y_{1}+l_{2}(x)\cdot y_{2}$ ，其中

$\left\{\begin{matrix} l_{0}(x_{0})=1, &l_{0}(x_{1})=0, &l_{0}(x_{2})=0 \\ l_{1}(x_{0})=0,& l_{1}(x_{1})=1, & l_{1}(x_{2})=0 \\ l_{2}(x_{0})=0,& l_{2}(x_{1})=0 & l_{2}(x_{2})=1 \end{matrix}\right.$ , 满足插值条件。

先求 $l_{0}(x)$ ，设 $l_{0}(x)=A(x-x_{1})\cdot (x-x_{2})$ 又由 $l_{0}(x_{0}) = 1\Rightarrow A=\frac{1}{(x_{0}-x_{1})(x_{0}-x_{2})}$ ，将A的值回代得 $l_{0}(x) = \frac{(x-x_{1})(x-x_{2})}{(x_{0}-x_{1})(x_{0}-x_{2})}$ ,

同理可得： $l_{1}(x) = \frac{(x-x_{0})(x-x_{2})}{(x_{1}-x_{0})(x_{1}-x_{2})}$ ， $l_{2}(x) = \frac{(x-x_{0})(x-x_{1})}{(x_{2}-x_{0})(x_{2}-x_{1})}$

3、拉格朗日插值多项式

定理：满足插值条件 $\varphi (x_{i} )= y_{i}(i = 0, 1, \cdots ,n)$ 的 $n$ 次拉格朗日插值多项式为：

$L_{n}(x) = \sum_{i = 0}^{n}l_{i}(x)\cdot y_{i}$ ，其中 $l_{i}(x) = \prod_{j=0,j\neq i}^{n}\frac{x-x_{j}}{x_{i}-x_{j}}$

特殊的：n=1为线性插值，n=2为抛物线插值。

下面是我自己写的C++代码

C++代码为：

#include<iostream>
#include<vector>
#include"Larange.h"
using namespace std;

int main()
{
 double x[] = { 0, 3, 5, 7, 9, 11, 12, 13, 14, 15 };
 double y[] = { 0, 1.2, 1.7, 2.0, 2.1, 2.0, 1.8, 1.2, 1.0, 1.6 };
 int  length = sizeof(x) / sizeof(x[0]);
 vector<double> arrX, arrY;
 for (int i = 0; i < length; i++) {
  arrX.push_back(x[i]);
  arrY.push_back(y[i]);
 }
 int length1 = arrX.size();
 double X;
 cout << "请输入待求解的插值点的X值，待解X = " ;
 cin >> X;
 cout << endl;

 double result = Larange(arrX, arrY, length, X);

 cout << "lagrange法求得的X对应的函数值为，y = " << result << endl;
 cout << "Hello World !" << endl;
}

头文件 $Lagrange.h$ 的代码，也就是拉格朗日算法实现部分代码为：

#pragma once
#include<vector>
using namespace std;

double Larange(vector<double> &arrX, vector<double> &arrY, int &length, double &X) {
 double yResult = 0;      //计算结果初始化
 vector<double> LResult;     //将每个基函数存储起来

 for (int i = 0; i < length; i++) {
  double Molecule = 1.0;            //分子累乘积
  double Denominator = 1.0;  //分母累乘积
  for (int j = 0; j < length; j++) {
   if (i == j)
    continue;   //  i!=j
   Molecule *= (X - arrX[j]);
   Denominator *= (arrX[i] - arrX[j]);
  }
  double L = Molecule / Denominator;
  LResult.push_back(L);
 }

 for (int i = 0; i < length; i++) {
  yResult += arrY[i] * LResult[i];
 }
 return yResult;
}

关于matlab的拉格朗日算法代码，由于matlab中有它的函数，所以不再多说了。

数值计算笔记之插值(一）拉格朗日插值

0、插值的概念

一、拉格朗日插值法

浏览过的版块