詳解Python牛頓插值法
一、牛頓多項式
拉格朗日多項式的公式不具備遞推性,每個多項式需要單獨構造。但很多時候我們需要從若幹個逼近多項式選擇一個。這個時候我們就需要一個具有遞推關系的方法來構造——牛頓多項式
這裡的的a0,a1…等可以通過逐一帶入點的值來求得。但是當項數多起來時,會發現式子變得很大,這個時候我們便要引入差商的概念(利用差分思想)具體見式子能更好理解
這裡在編程實現中我們可以推出相應的差商推導方程
d(k,0)=y(k)
d(k,j)=(d(k,j-1)-d(k-1,j-1)) / (x(k)-x(k-j))
二、例題
【問題描述】考慮[0,3]內的函數y=f(x)=cos(x)。利用多個(最多為6個)節點構造牛頓插值多項式。
【輸入形式】在屏幕上依次輸入在區間[0,3]內的一個值x*,構造插值多項式後求其P(x*)值,和多個節點的x坐標。
【輸出形式】輸出牛頓插值多項式系數向量,差商矩陣,P(x*)值(保留6位有效數字),和與真實值的絕對誤差(使用科學計數法,保留小數點後6位有數字)。
【樣例1輸入】
0.8
0 0.5 1
【樣例1輸出】
-0.429726
-0.0299721
1
1 0 0
0.877583 -0.244835 0
0.540302 -0.674561 -0.429726
0.700998
4.291237e-03
【樣例1說明】
輸入:x為0.8,3個節點為(k, cos(k)),其中k = 0, 0.5, 1。
輸出:
牛頓插值多項式系數向量,表示P2(x)=-0.429726x^2 – 0.0299721x + 1;
3行3列的差商矩陣;
當x為0.8時,P2(0.8)值為0.700998
與真實值的絕對誤差為:4.291237*10^(-3)
【評分標準】根據輸入得到的輸出準確
三、ACcode:
C++(後面還有python代碼)
/* * @Author: csc * @Date: 2021-04-30 08:52:45 * @LastEditTime: 2021-04-30 11:57:46 * @LastEditors: Please set LastEditors * @Description: In User Settings Edit * @FilePath: \code_formal\course\cal\newton_quo.cpp */ #include <bits/stdc++.h> #define pr printf #define sc scanf #define for0(i, n) for (i = 0; i < n; i++) #define for1n(i, n) for (i = 1; i <= n; i++) #define forab(i, a, b) for (i = a; i <= b; i++) #define forba(i, a, b) for (i = b; i >= a; i--) #define pb push_back #define eb emplace_back #define fi first #define se second #define int long long #define pii pair<int, int> #define vi vector<int> #define vii vector<vector<int>> #define vt3 vector<tuple<int, int, int>> #define mem(ara, n) memset(ara, n, sizeof(ara)) #define memb(ara) memset(ara, false, sizeof(ara)) #define all(x) (x).begin(), (x).end() #define sq(x) ((x) * (x)) #define sz(x) x.size() const int N = 2e5 + 100; const int mod = 1e9 + 7; namespace often { inline void input(int &res) { char c = getchar(); res = 0; int f = 1; while (!isdigit(c)) { f ^= c == '-'; c = getchar(); } while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48); c = getchar(); } res = f ? res : -res; } inline int qpow(int a, int b) { int ans = 1, base = a; while (b) { if (b & 1) ans = (ans * base % mod + mod) % mod; base = (base * base % mod + mod) % mod; b >>= 1; } return ans; } int fact(int n) { int res = 1; for (int i = 1; i <= n; i++) res = res * 1ll * i % mod; return res; } int C(int n, int k) { return fact(n) * 1ll * qpow(fact(k), mod - 2) % mod * 1ll * qpow(fact(n - k), mod - 2) % mod; } int exgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int res = exgcd(b, a % b, x, y); int t = y; y = x - (a / b) * y; x = t; return res; } int invmod(int a, int mod) { int x, y; exgcd(a, mod, x, y); x %= mod; if (x < 0) x += mod; return x; } } using namespace often; using namespace std; int n; signed main() { auto polymul = [&](vector<double> &v, double er) { v.emplace_back(0); vector<double> _ = v; int m = sz(v); for (int i = 1; i < m; i++) v[i] += er * _[i - 1]; }; auto polyval = [&](vector<double> const &c, double const &_x) -> double { double res = 0.0; int m = sz(c); for (int ii = 0; ii < m; ii++) res += c[ii] * pow(_x, (double)(m - ii - 1)); return res; }; int __ = 1; //input(_); while (__--) { double _x, temp; cin >> _x; vector<double> x, y; while (cin >> temp) x.emplace_back(temp), y.emplace_back(cos(temp)); n = x.size(); vector<vector<double>> a(n, vector<double>(n)); int i, j; for0(i, n) a[i][0] = y[i]; forab(j, 1, n - 1) forab(i, j, n - 1) a[i][j] = (a[i][j - 1] - a[i - 1][j - 1]) / (x[i] - x[i - j]); vector<double> v; v.emplace_back(a[n - 1][n - 1]); forba(i, 0, n - 2) { polymul(v, -x[i]); int l = sz(v); v[l - 1] += a[i][i]; } for0(i, n) pr("%g\n", v[i]); for0(i, n) { for0(j, n) pr("%g ", a[i][j]); puts(""); } double _y = polyval(v, _x); pr("%g\n", _y); pr("%.6e",fabs(_y-cos(_x))); } return 0; }
python代碼
''' Author: csc Date: 2021-04-29 23:00:57 LastEditTime: 2021-04-30 09:58:07 LastEditors: Please set LastEditors Description: In User Settings Edit FilePath: \code_py\newton_.py ''' import numpy as np def difference_quotient(x, y): n = len(x) a = np.zeros([n, n], dtype=float) for i in range(n): a[i][0] = y[i] for j in range(1, n): for i in range(j, n): a[i][j] = (a[i][j-1]-a[i-1][j-1])/(x[i]-x[i-j]) return a def newton(x, y, _x): a = difference_quotient(x, y) n = len(x) s = a[n-1][n-1] j = n-2 while j >= 0: s = np.polyadd(np.polymul(s, np.poly1d( [x[j]], True)), np.poly1d([a[j][j]])) j -= 1 for i in range(n): print('%g' % s[n-1-i]) for i in range(n): for j in range(n): print('%g' % a[i][j], end=' ') print() _y = np.polyval(s, _x) print('%g' % _y) # re_err real_y = np.cos(_x) err = abs(_y-real_y) print('%.6e' % err) def main(): _x = float(input()) x = list(map(float, input().split())) y = np.cos(x) newton(x, y, _x) if __name__ == '__main__': main()
到此這篇關於詳解Python牛頓插值法的文章就介紹到這瞭,更多相關Python牛頓插值法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Python用二分法求平方根的案例
- C++編譯原理之求解First集合
- C++ stringstream格式化輸出輸入詳情
- 帶你瞭解C++中vector的用法
- C++ STL標準庫std::vector的使用詳解