牛頓試演算法
❶ 什麼是牛頓演算法
已經編譯運行確認：
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
typedef struct data
{
float x;
float y;
}Data;//變數x和函數值y的結構
Data d[20];//最多二十組數據
float f(int s,int t)//牛頓插值法，用以返回插商
{
if(t==s+1)
return (d[t].y-d[s].y)/(d[t].x-d[s].x);
else
return (f(s+1,t)-f(s,t-1))/(d[t].x-d[s].x);
}
float Newton(float x,int count)
{
int n;
while(1)
{
cout<<"請輸入n值(即n次插值):";//獲得插值次數
cin>>n;
if(n<=count-1)// 插值次數不得大於count－1次
break;
else
system("cls");
}
//初始化t，y，yt。
float t=1.0;
float y=d[0].y;
float yt=0.0;
//計算y值
for(int j=1;j<=n;j++)
{
t=(x-d[j-1].x)*t;
yt=f(0,j)*t;
//cout<<f(0,j)<<endl;
y=y+yt;
}
return y;
}
float lagrange(float x,int count)
{
float y=0.0;
for(int k=0;k<count;k++)//這兒默認為count－1次插值
{
float p=1.0;//初始化p
for(int j=0;j<count;j++)
{//計算p的值
if(k==j)continue;//判斷是否為同一個數
p=p*(x-d[j].x)/(d[k].x-d[j].x);
}
y=y+p*d[k].y;//求和
}
return y;//返回y的值
}
void main()
{
float x,y;
int count;
while(1)
{
cout<<"請輸入x[i],y[i]的組數，不得超過20組:";//要求用戶輸入數據組數
cin>>count;
if(count<=20)
break;//檢查輸入的是否合法
system("cls");
}
//獲得各組數據
for(int i=0;i<count;i++)
{
cout<<"請輸入第"<<i+1<<"組x的值:";
cin>>d[i].x;
cout<<"請輸入第"<<i+1<<"組y的值:";
cin>>d[i].y;
system("cls");
}
cout<<"請輸入x的值:";//獲得變數x的值
cin>>x;
while(1)
{
int choice=3;
cout<<"請您選擇使用哪種插值法計算："<<endl;
cout<<" (0):退出"<<endl;
cout<<" (1):Lagrange"<<endl;
cout<<" (2):Newton"<<endl;
cout<<"輸入你的選擇：";
cin>>choice;//取得用戶的選擇項
if(choice==2)
{
cout<<"你選擇了牛頓插值計算方法，其結果為：";
y=Newton(x,count);break;//調用相應的處理函數
}
if(choice==1)
{
cout<<"你選擇了拉格朗日插值計算方法，其結果為：";
y=lagrange(x,count);break;//調用相應的處理函數
}
if(choice==0)
break;
system("cls");
cout<<"輸入錯誤!!!!"<<endl;
}
cout<<x<<" , "<<y<<endl;//輸出最終結果
}
❷ 牛頓法的時間復雜度是什麼
牛頓法的時間復雜度是：
時間復雜性，又稱時間復雜度，演算法的時間復雜度是一個函數，它定性描述該演算法的運行時間。這是一個代表演算法輸入值的字元串的長度的函數。
時間復雜度常用大O符號表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間復雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。
時間復雜度的次指數時間：
術語次指數時間用於表示某些演算法的運算時間可能比任何多項式增長得快，但仍明顯小於指數。在這種狀況下，具有次指數時間演算法的問題比那些僅具有指數演算法的問題更容易處理。「次指數」的確切定義並沒有得到普遍的認同，我們列出了以下兩個最廣泛使用的。
❸ 牛頓迭代法的牛頓迭代公式
設r是的根，選取作為r的初始近似值，過點做曲線的切線L，L的方程為，求出L與x軸交點的橫坐標，稱x1為r的一次近似值。過點做曲線的切線，並求該切線與x軸交點的橫坐標，稱為r的二次近似值。重復以上過程，得r的近似值序列，其中，稱為r的次近似值，上式稱為牛頓迭代公式。
用牛頓迭代法解非線性方程，是把非線性方程線性化的一種近似方法。把在點的某鄰域內展開成泰勒級數，取其線性部分（即泰勒展開的前兩項），並令其等於0，即，以此作為非線性方程的近似方程，若，則其解為， 這樣，得到牛頓迭代法的一個迭代關系式：。
已經證明，如果是連續的，並且待求的零點是孤立的，那麼在零點周圍存在一個區域，只要初始值位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。
軍人在進攻時常採用交替掩護進攻的方式，若在數軸上的點表示A，B兩人的位置，規定在前面的數大於後面的數，則是A>B，B>A交替出現。但現在假設軍中有一個膽小鬼，同時大家又都很照顧他，每次沖鋒都是讓他跟在後面，每當前面的人占據一個新的位置，就把位置交給他，然後其他人再往前佔領新的位置。也就是A始終在B的前面，A向前邁進，B跟上，A把自己的位置交給B（即執行B = A），然後A 再前進佔領新的位置，B再跟上，直到佔領所有的陣地，前進結束。像這種兩個數一前一後逐步向某個位置逼近的方法稱為迭代法。
迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程，跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）重復執行，在每次執行這組指令（或這些步驟）時，都從變數的原值推出它的一個新值。
利用迭代演算法解決問題，需要做好以下三個方面的工作：
一、確定迭代變數
在可以用迭代演算法解決的問題中，至少存在一個可直接或間接地不斷由舊值遞推出新值的變數，這個變數就是迭代變數。
二、建立迭代關系式
所謂迭代關系式，指如何從變數的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。
三、對迭代過程進行控制
在什麼時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對於前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對於後一種情況，需要進一步分析得出可用來結束迭代過程的條件。
❹ 牛頓迭代法的示例
最經典的迭代演算法是歐幾里德演算法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b。假設d是a,b的一個公約數，則有 a%d==0,b%d==0，而r = a - kb，因此r%d==0 ，因此d是(b,a mod b)的公約數
同理，假設d 是(b,a mod b)的公約數，則 b%d==0,r%d==0 ，但是a = kb +r ，因此d也是(a,b)的公約數。
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。
歐幾里德演算法就是根據這個原理來做的，歐幾里德演算法又叫輾轉相除法，它是一個反復迭代執行，直到余數等於0停止的步驟，這實際上是一個循環結構。其演算法用C語言描述為： intGcd_2(inta,intb)/*歐幾里德演算法求a,b的最大公約數*/{if(a<=0||b<=0)/*預防錯誤*/return0;inttemp;while(b>0)/*b總是表示較小的那個數，若不是則交換a，b的值*/{temp=a%b;/*迭代關系式*/a=b;b=temp;}returna;}從上面的程序我們可以看到a，b是迭代變數，迭代關系是temp = a % b；根據迭代關系我們可以由舊值推出新值，然後循環執a = b; b = temp；直到迭代過程結束（余數為0）。在這里a好比那個膽小鬼，總是從b手中接過位置，而b則是那個努力向前沖的先鋒。 還有一個很典型的例子是斐波那契（Fibonacci）數列。斐波那契數列為：0、1、1、2、3、5、8、13、21、…，即 fib⑴=0; fib⑵=1;fib(n)=fib(n-1)+fib(n-2) （當n>2時）。
在n>2時，fib(n)總可以由fib(n-1)和fib(n-2)得到，由舊值遞推出新值，這是一個典型的迭代關系，所以我們可以考慮迭代演算法。 intFib(intn)//斐波那契（Fibonacci）數列{if(n<1）/*預防錯誤*/return0;if(n==1||n==2)/*特殊值，無需迭代*/return1;intf1=1,f2=1,fn;/*迭代變數*/inti;for(i=3;i<=n;++i)/*用i的值來限制迭代的次數*/{fn=f1+f2;/*迭代關系式*/f1=f2;//f1和f2迭代前進，其中f2在f1的前面f2=fn;}returnfn;}
❺ 求平方根的牛頓演算法
首先我們設要求的這個數為a，它的平方根為x；然後我們一開始令x=a；然後我們進入一個循環，不斷的令x=(x+a/x)/2，就是令x等於 x和a/x的平均值，這樣迭代了7-10次左右就可以得到a的平方根x的近似值。
❻ 牛頓迭代公式有關演算法
牛頓迭代法求方程的一個實根
牛頓公式：x(k+1) = x(k) - f(x(k)) / f '(x(k))
迭代函數：Ф(x) = x - f(x) / f'(x)
屬性：方程求根迭代法
此時的迭代函數必須保證X(k)有極限，即迭代收斂。
《數值計算方法與演算法》-2 Editon -科學出版社 P93
《C#數值計算演算法編程》-周長發 P210
代碼維護：2007.04.20 pengkuny
**/
#include<iostream>
#include<cmath>
using namespace std;
#define f(x) (x*x*(x-1.0)-1.0) //舉例函數x^3-x^2-1
#define g(x) (3.0*x*x-2.0*x) //導函數3x^2-2x
#define epsilon 0.0000001 //精度
#define MAXREAPT 100
bool RootNewton(double &x)
{
double xk1,xk0;
xk0 = x;
for (int k=0; k<MAXREAPT; k++)
{
if (g(xk0) == 0.0)//牛頓迭代法缺陷在於:收斂是否與初值x0密切相關
{//如果g(xk0)數值特別小時,有可能發生從一個根跳到另一個根附近的情況
cout<<"迭代過程中導數為0."<<endl;
return false;
}
xk1 = xk0 - f(xk0)/g(xk0);//key step
if (fabs(xk1-xk0) < epsilon && fabs(f(xk1)) < epsilon)
{//注意迭代結束條件是: |f(xk1)| < ε和|xk1-xk0| < ε同時成立,防止根跳躍
x = xk1;
return true;
}
else
{
xk0 = xk1;
}
}
//迭代失敗
cout<<"迭代次數超過預期."<<endl;
return false;
}
int main()
{
double x;
cout<<"牛頓迭代法求方程根,請輸入初始迭代x0值:"<<endl;
cin>>x;
if(RootNewton(x))
{
cout<<"該值附近的根為:"<<x<<endl;
}
else
{
cout<<"迭代失敗!"<<endl;
}
system("pause");
return 0;
}
❼ 什麼是高斯-牛頓演算法
用於解無約束最優化問題的
在解非線性方程組時,處理困難.因此用一個線性逼近(我理解是相似).
具體可以看運籌學或者是最優化書籍相關章節.
如果你已經看過了，那我也無能為力
❽ 大一計算機專業應該掌握的演算法有哪些
大一的話不用掌握太專一的演算法，主要是真正理解程序設計的3中流程，知道數組能幹哪些事情，嘗試理解函數遞歸，理解RAM機模型。掌握以下基本演算法：
篩選法、試除法求素數，漢諾塔，放蘋果，簡單枚舉法，N皇後問題等簡單回溯法，簡單模擬法，高精度演算法（+-*/），GCD演算法，二分法、牛頓發求根，選擇、冒泡排序等基本演算法。
一開始，學會用程序表達自己的演算法思想是最基本的基本功。
年級高了以後，等你學了離散數學。數據結構，演算法設計與分析以後，就能設計些較復雜的演算法了。
推薦幾本書：
演算法導論，英文叫Introction to Algorithms,2nd Edition，這個很經典
計算機程序設計藝術，這個也是經典著作，最好看看
數據結構與演算法分析
如果你們學校有ACM校隊的話最好和他們交流交流。
❾ 數學牛頓迭代法的例子
牛頓迭代公式編輯
設r是
的根，選取
作為r的初始近似值，過點
做曲線
的切線L，L的方程為
，求出L與x軸交點的橫坐標
，稱x1為r的一次近似值。過點
做曲線
的切線，並求該切線與x軸交點的橫坐標
，稱
為r的二次近似值。重復以上過程，得r的近似值序列，其中，
稱為r的
次近似值，上式稱為牛頓迭代公式。
用牛頓迭代法解非線性方程，是把非線性方程
線性化的一種近似方法。把
在點
的某鄰域內展開成泰勒級數
，取其線性部分（即泰勒展開的前兩項），並令其等於0，即
，以此作為非線性方程
的近似方程，若
，則其解為
， 這樣，得到牛頓迭代法的一個迭代關系式：
。
已經證明，如果是連續的，並且待求的零點是孤立的，那麼在零點周圍存在一個區域，只要初始值位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。[1]
軍人在進攻時常採用交替掩護進攻的方式，若在數軸上的點表示A，B兩人的位置，規定在前面的數大於後面的數，則是A>B，B>A交替出現。但現在假設軍中有一個膽小鬼，同時大家又都很照顧他，每次沖鋒都是讓他跟在後面，每當前面的人占據一個新的位置，就把位置交給他，然後其他人再往前佔領新的位置。也就是A始終在B的前面，A向前邁進，B跟上，A把自己的位置交給B（即執行B = A），然後A 再前進佔領新的位置，B再跟上，直到佔領所有的陣地，前進結束。像這種兩個數一前一後逐步向某個位置逼近的方法稱為迭代法。
迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程，跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）重復執行，在每次執行這組指令（或這些步驟）時，都從變數的原值推出它的一個新值。
利用迭代演算法解決問題，需要做好以下三個方面的工作：
一、確定迭代變數
在可以用迭代演算法解決的問題中，至少存在一個可直接或間接地不斷由舊值遞推出新值的變數，這個變數就是迭代變數。
二、建立迭代關系式
所謂迭代關系式，指如何從變數的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。
三、對迭代過程進行控制
在什麼時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對於前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對於後一種情況，需要進一步分析得出可用來結束迭代過程的條件。
❿ 牛頓迭代方法
牛頓迭代法（Newton's method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀提出的一種在實數域和復數域上近似求解方程的方法。
中文名
牛頓迭代法
外文名
Newton's method
別名
牛頓-拉夫遜（拉弗森）方法
提出時間
17世紀
快速
導航
牛頓迭代公式
其他迭代演算法
C語言代碼
C++代碼
matlab代碼
Python代碼
Java代碼
JavaScript代碼
Fortran代碼
產生背景
多數方程不存在求根公式，因此求精確根非常困難，甚至不可解，從而尋找方程的近似根就顯得特別重要。方法使用函數 的泰勒級數的前面幾項來尋找方程 的根。牛頓迭代法是求方程根的重要方法之一，其最大優點是在方程 的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復根，此時線性收斂，但是可通過一些方法變成超線性收斂。另外該方法廣泛用於計算機編程中。
牛頓迭代公式
設 是 的根，選取 作為 的初始近似值，過點 做曲線 的切線 ， ，則 與 軸交點的橫坐標 ，稱 為 的一次近似值。過點 做曲線 的切線，並求該切線與x軸交點的橫坐標 ，稱 為r的二次近似值。重復以上過程，得 的近似值序列，其中， 稱為 的 次近似值，上式稱為牛頓迭代公式。
用牛頓迭代法解非線性方程，是把非線性方程 線性化的一種近似方法。把 在點 的某鄰域內展開成泰勒級數 ，取其線性部分（即泰勒展開的前兩項），並令其等於0，即 ，以此作為非線性方程 的近似方程，若 ，則其解為 ， 這樣，得到牛頓迭代法的一個迭代關系式： 。
已經證明，如果是連續的，並且待求的零點是孤立的，那麼在零點周圍存在一個區域，只要初始值位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。
迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程，跟迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）重復執行，在每次執行這組指令（或這些步驟）時，都從變數的原值推出它的一個新值。
利用迭代演算法解決問題，需要做好以下三個方面的工作：
一、確定迭代變數
在可以用迭代演算法解決的問題中，至少存在一個可直接或間接地不斷由舊值遞推出新值的變數，這個變數就是迭代變數。
二、建立迭代關系式
所謂迭代關系式，指如何從變數的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。
三、對迭代過程進行控制
在什麼時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對於前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對於後一種情況，需要進一步分析得出可用來結束迭代過程的條件。
其他迭代演算法
歐幾里德演算法
最經典的迭代演算法是歐幾里德演算法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b。假設d是a,b的一個公約數，則有 a%d==0,b%d==0，而r = a - kb，因此r%d==0 ，因此d是(b,a mod b)的公約數
查看更多