Міністерство освіти та науки України Національний університет “Львівська політехніка” Звіт про виконання лабораторної роботи N3 з курсу “Алгоритмічні основи криптології” на тему: “Метод Ньютона для розв’язування систем нелінійних рівнянь ” Львів – 2004 Мета роботи: ознайомитися з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона. Завдання: написати програму на мові програмування Сі яка б розв’язувала систему нелінійних рівнянь модифікованим методом Ньютона, реалізувати обертання матриць методом Гауса, а обчислення похідних методом кінцевих різниць. x1 = x12 – x22 – 0.1 , x2 = 2x1x2 + 0.1 , x10 = 0, x20 = 0, Блок – схема алгоритму роботи програми Текст програми: #include<stdio.h> #include<math.h> #include<conio.h> #define n 2 #define er 0.00001 #define h 10e-9 static float JacP[n+2][n+2],Jacobi[n+2][n+2]; /* Fynkcija obertannja matruci met. Gausa*/ Gaus(float a[n+2][n+2]) { int i,k,d,f; float aa[n+2][n+2],b[n+1]; float s=0; for(f=1;f<=n;f++) { for (i=1;i<=n;i++) { if (f==i) b[i]=1; else b[i]=0; a[i][n+1]=((-1)*b[i]); } for(d=1;d<=(n-1);d++) for(i=d+1;i<=n;i++) for(k=d+1;k<=(n+1);k++) { aa[d][k]=((-1)*a[d][k]/a[d][d]); a[i][k]=(a[i][d]*aa[d][k])+a[i][k]; } Jacobi[n][f]=(-1)*a[n][n+1]/a[n][n]; for(i=n-1;i>=1;i--) { for (k=i+1;k<=n;k++) s+=aa[i][k]*JacP[n][f]; Jacobi[n-1][f]=aa[i][n+1]+s; s=0; } } return(Jacobi[n+2][n+2]); } /*Fynkcija vuznachennja znachen' fynkcii*/ float func(float x1,float x2,int i) { if (i==1) return (x1-(x1*x1)+(x2*x2)+0.1); else return (x2-(2*x1*x2)-0.1); } /*Vukonannja samoi programu*/ void main(void) { int i,j; float x[n+2]; int m; float Max,x1,y1,s1; x[1]=0; x[2]=0; do { x1=x[1]; y1=x[2]; /*Vuznachennja znachennja poxidnux met. kincevux riznuc'*/ for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if (j==1) JacP[i][j] = (func(x[j]+h,x[j+1],i)-func(x[j],x[j+1],i))/h; else JacP[i][j] = (func(x[1],x[j]+h,i)-func(x[1],x[j],i))/h; } /*Vukonannja funkcii Gaus*/ Gaus(JacP); for (i=1;i<=n;i++) { s1=0; for (j=1;j<=n;j++) { if (j==1) Jacobi[i][j]*=func(x[j],x[j+1],i); else Jacobi[i][j]*=func(x[j-1],x[j],i); s1+=Jacobi[i][j]; } if (i==1) x[i]=x1-s1; else x[i]=y1-s1; } /*Perevirka poxubku*/ Max=fabs((x[1]-x1)/x[1]); if (fabs((x[2]-y1)/x[2])>Max) Max=fabs((x[2]-y1)/x[2]); if(Max<er) { m=1;break; } else m=0; } while (m!=1); for(i=1;i<=n;i++) { printf ("\nx[%d]=%2.5f",i,x[i]); } printf ("\n f1 = (x1-(x1*x1)+(x2*x2)+0.1) = %f" , (x[1]-(x[1]*x[1])+(x[2]*x[2])+0.1)); printf ("\n f2 = (x2-(2*x1*x2)-0.1) = %f" , (x[2]-(2*x[1]*x[2])-0.1)); Результат виконання програми:
Висновок: Розв’язання систем нелінійних алгебраїчних рівнянь методом Ньютона можна досить легко реалізувати на ЕОМ за допомогою програми в середовищі Сі. Основна перевага модифікованого методу Ньютона полягає в тому, що при використанні цього методу якобіан замінюють правильно підібраною матрицею, яку зберігають сталою протягом деякого числа ітерацій, а потім на певній ітерації її заново обчислюють і присвоюють знайдене значення якобіану. Це дозволяє значно зекономити машинний час виконання програми. Розв’язання таких систем на ЕОМ є дуже актуальним, оскільки цей процес є набагато легшим та короткотривалішим ніж розв’язання систем нелінійних рівнянь вручну.