طريقة الإنكماش

 طريقة الإنكماش

---

مصطلحات

العربية: طريقة الإنكماش

الإنجليزية: Deflation Method
الفرنسية: Méthode de déflation

---

المبدأ

(حالة  )

نفترض معرفة الزوج (₁, x₁)، قيمة المميزة لأكبر معيار A ومتجهة المميزة المرتبطة(حسبة عامة بطريقة القوى). إذن يمكننا حساب ₂ ،القيمة المميزة للمعيار  الأدنى مباشرة من₁، بتحويل المصفوفة A إلى مصفوفةA⁽¹⁾  ذات نفس القيم المميزة A إلا₁  المعوض بقيمة مميزة منعدمة،ثم نطبق من جديد طريقة القوى على A⁽¹⁾ .

---

الخوارزم

نفترض معرفة الزوج (₁, x₁)

نعتبر متجهة w بحيث 

لتكن A⁽¹⁾ = A - ₁ x₁ w^T

نطبق من جديد طريقة القوى علىA⁽¹⁾ ،بحساب (₂, v₂) و( v₂متجهة مميزةل A⁽¹⁾) ونستنتجالمتجهة المميزة لA الملائمة لصيغة:

يمكن تكرار الانكماش علىA⁽¹⁾ ،وهكدا.

---

 مثال

أحسب القيمتين المميزتين لأكبر معيار (ومتجهة المميزة المرتبطة) للمصفوفة:

نختار اعتباطيا متجهة الانطلاقة:

 

وv لأول متجهة القاعدة القانونية.

حساب الانكماش: 

نحسب أول زوج قيمة /متجهة بطريقة القوى

نختار 

A⁽¹⁾ = A - ₁ x₁ w^T

---

البرمجة

نسترجع برنامج طريقة القوى، ونكمله بالانكماش:

#include <math.h>
#include <conio.h>
#define NMAX 5
 
double al_norme_vect(double x[NMAX],int n);
void al_prod_mat_vect(double a[NMAX][NMAX],int n,double x[NMAX],double y[NMAX]);
 double vp_puissance(double a[NMAX][NMAX],int n,double x[NMAX],double eps);

main()
{
 double x[NMAX],r[NMAX],w[NMAX],v[NMAX];
 double a[NMAX][NMAX],b[NMAX][NMAX];
 double l1,l2,eps,tx;
 int i,j,n;
 clrscr();
 printf("Méthode de la Puissance avec déflation\n");
 n=4;
 a[1][1]=-183;a[1][2]=53;a[1][3]=-12;a[1][4]=28;
 a[2][1]=-392;a[2][2]=113;a[2][3]=-38;a[2][4]=65;
 a[3][1]=-192;a[3][2]=56;a[3][3]=-1;a[3][4]=25;
 a[4][1]=-538;a[4][2]=157;a[4][3]=-7;a[4][4]=71;
 printf("Matrice A\n");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
  printf("%12.6e ",a[i][j]);
  printf("\n");
 }
 eps=1e-13;
 printf("Les premiers itérés :\n");
 for(i=1;i<=n;i++)
 x[i]=1;
 l1=vp_puissance(a,n,x,eps);
 printf("1er couple valeur/vecteur propre (dernier itéré)\n");
 printf("lambda1 = %22.16e\n",l1);
 printf("x(1) = ");
 for(i=1;i<=n;i++)
 printf("\n %22.16e  ",x[i]);
 printf("\n");
 al_prod_mat_vect(a,n,x,r);
 for(i=1;i<=n;i++)
 r[i] -= l1*x[i];
 printf("Norme résidu = %.3e\n",al_norme_vect(r,n));
 printf("Déflation\n");
 tx=al_norme_vect(x,n);
 tx=tx*tx;
 for(i=1;i<=n;i++)
 w[i]=x[i]/tx;
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 b[i][j]=a[i][j]-l1*x[i]*w[j];
 printf("Matrice A(1)\n");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
  printf("%12.6e ",b[i][j]);
  printf("\n");
 }
 printf("Les premiers itérés :\n");
 for(i=1;i<=n;i++)
 v[i]=1;
 l2=vp_puissance(b,n,v,eps);
 printf("2e couple valeur/vecteur propre (dernier itéré)\n");
 printf("lambda2 = %22.16e\n",l2);
 printf("v(2) = ");
 for(i=1;i<=n;i++)
 printf("\n %22.16e  ",v[i]);
 printf("\n");
 al_prod_mat_vect(b,n,v,r);
 for(i=1;i<=n;i++)
 r[i] -= l2*v[i];
 printf("Norme résidu (pour A(1)) = %.3e\n",al_norme_vect(r,n));
 tx=0.0;
 for(i=1;i<=n;i++)
 tx+=w[i]*v[i];
 tx*=l1/(l2-l1);
 printf("x(2) = ");
 for(i=1;i<=n;i++)
 {
  x[i]=v[i]+tx*x[i];
  printf("\n %22.16e  ",x[i]/x[1]);
 }
 printf("\n");
  al_prod_mat_vect(a,n,x,r);
 for(i=1;i<=n;i++)
 r[i] -= l2*x[i];
 printf("Norme résidu = %.3e\n",al_norme_vect(r,n)/x[1]);
}

---

نتيجة البرنامج

نسترجع إظهار طرقة القوى، ثم نطبق الانكماش

نحذف التعليقات من الدالة  vp_puissance؛ في كل كرة البرنامج يظهر :

• المعاد l^(k)
• المعادu^(k+1) 

ثم يظهر بعد ذلك الانكماش

• آخر كرة
• متجهة المميزة x لـ A الملائم لـ v
•  ضابطة الباقي Ax -  x

طريقة القوى مع الانكماش

 A                المصفوفة 
-1.83000e+02  5.30000e+01 -1.20000e+01  2.80000e+01 
-3.92000e+02  1.13000e+02 -3.80000e+01  6.50000e+01 
-1.92000e+02  5.60000e+01 -1.00000e+00  2.50000e+01 
-5.38000e+02  1.57000e+02 -7.00000e+00  7.10000e+01 
الكرة الأولى
l(  1)=-1.1400e+02   u(  1)=( 1.0000e+00  2.2105e+00  9.8246e-01  2.7807e+00 )
l(  2)= 2.2807e-01   u(  2)=( 1.0000e+00  5.2692e+00  1.4231e+00 -1.7308e+00 )
l(  3)= 3.0731e+01   u(  3)=( 1.0000e+00  1.1990e+00  1.8999e+00  5.0901e+00 )
l(  4)= 2.7159e-01   u(  4)=( 1.0000e+00  7.9124e+00  1.8295e+00 -6.1060e+00 )
l(  5)= 4.3438e+01   u(  5)=( 1.0000e+00  8.2177e-01  2.2243e+00  5.9377e+00 )
l( 10)=-2.2872e-01   u( 10)=( 1.0000e+00 -9.1163e+00  2.3037e+00  2.2607e+01 )
l( 20)=-1.0548e+00   u( 20)=( 1.0000e+00 -1.4301e+00  2.2966e+00  9.7508e+00 )
l( 30)=-1.7893e+00   u( 30)=( 1.0000e+00 -5.5632e-01  2.2964e+00  8.2898e+00 )
l( 40)=-2.3874e+00   u( 40)=( 1.0000e+00 -2.4193e-01  2.2964e+00  7.7641e+00 )
l( 50)=-2.8403e+00   u( 50)=( 1.0000e+00 -9.1986e-02  2.2964e+00  7.5134e+00 )
l( 60)=-3.1646e+00   u( 60)=( 1.0000e+00 -1.0974e-02  2.2964e+00  7.3779e+00 )
l( 70)=-3.3877e+00   u( 70)=( 1.0000e+00  3.5751e-02  2.2964e+00  7.2998e+00 )
l( 80)=-3.5370e+00   u( 80)=( 1.0000e+00  6.3723e-02  2.2964e+00  7.2530e+00 )
l( 90)=-3.6351e+00   u( 90)=( 1.0000e+00  8.0842e-02  2.2964e+00  7.2244e+00 )
l(100)=-3.6986e+00   u(100)=( 1.0000e+00  9.1461e-02  2.2964e+00  7.2066e+00 )
l(110)=-3.7396e+00   u(110)=( 1.0000e+00  9.8103e-02  2.2964e+00  7.1955e+00 )
l(120)=-3.7658e+00   u(120)=( 1.0000e+00  1.0228e-01  2.2964e+00  7.1886e+00 )
l(130)=-3.7825e+00   u(130)=( 1.0000e+00  1.0491e-01  2.2964e+00  7.1842e+00 )
l(140)=-3.7931e+00   u(140)=( 1.0000e+00  1.0658e-01  2.2964e+00  7.1814e+00 )
l(150)=-3.7999e+00   u(150)=( 1.0000e+00  1.0763e-01  2.2964e+00  7.1796e+00 )
1er couple valeur/vecteur propre (dernier itéré)
lambda1 = -3.811646855752201e+00
x(1) = 
  1.000000000000000e+00  
  1.094572319901319e-01  
  2.296364144307056e+00  
  7.176553199301980e+00  
Norme résidu = 4.53e-13
Déflation
Matrice A(1)
-1.82934e+02  5.30072e+01 -1.18485e+01  2.84734e+01 
-3.91993e+02  1.13001e+02 -3.79834e+01  6.50518e+01 
-1.91849e+02  5.60166e+01 -6.52180e-01  2.60870e+01 
-5.37527e+02  1.57052e+02 -5.91300e+00  7.43971e+01 
Les premiers itérés :
l(  1)=-1.1330e+02   u(  1)=( 1.0000e+00  2.2235e+00  9.7436e-01  2.7536e+00 )
l(  2)= 1.7860e+00   u(  2)=( 1.0000e+00  7.7241e-01  2.1842e+00  6.0321e+00 )
l(  3)= 3.8843e+00   u(  3)=( 1.0000e+00  1.2170e+00  1.8933e+00  5.0556e+00 )
l(  4)= 3.0937e+00   u(  4)=( 1.0000e+00  8.0578e-01  2.2547e+00  5.9912e+00 )
l(  5)= 3.6541e+00   u(  5)=( 1.0000e+00  8.6509e-01  2.2199e+00  5.8624e+00 )
l( 10)= 3.6394e+00   u( 10)=( 1.0000e+00  7.8447e-01  2.2958e+00  6.0476e+00 )
l( 20)= 3.6421e+00   u( 20)=( 1.0000e+00  7.8408e-01  2.2963e+00  6.0485e+00 )
l( 30)= 3.6421e+00   u( 30)=( 1.0000e+00  7.8408e-01  2.2963e+00  6.0485e+00 )
2e couple valeur/vecteur propre (dernier itéré)
lambda2 =  3.642058168286467e+00
v(2) = 
  1.000000000000000e+00  
  7.840790390406579e-01  
  2.296281797754661e+00  
  6.048525233491739e+00  
Norme résidu (pour A(1)) = 2.08e-12
x(2) = 
  1.000000000000000e+00  
  1.314980606802037e+00  
  2.296216994166474e+00  
  5.160810354920547e+00  
Norme résidu = 3.50e-12

---

الدوال الثانوية

 معايير الدالة al_norme_vect هي كالتالي:

x :متجهة (التي فيها نحسب المنظم)n : بعد المتجهة.

ترجع هذه الدالة المنظم المتجهي الأقليدي (المنظم 2 لـ Holder).



معايير الدالة al_prod_mat_vect هي كالتالي:

a : المصفوفة
n : درجة المصفوفة
x و y : متجهتين

ترجع هذه الدالة في المتجهة y ضرب المصفوفة a في المتجهة x.



الدالة al_prod_matmd_vect

المصفوفة متماثلة قطريا، ومحفوظة في جدول ثنائي البعد بعده NMAX*NDIAG.

معايير الدالة هي كما يلي :

a : مصفوفة متماثلة قطريا ومكدسةn : درجة المصفوفةx و y : متجهتين

ترجع هذه الدالة في المتجهة y ضرب المصفوفة a في المتجهة x.

---

الدالة الرئيسية vp_puissance
معايير هذه الدالة هي كالتالي:

a : المصفوفة
n : درجة المصفوفة
x : جدول أحادي البعد
eps : الدقة المطلوبة

ترجع القيمة المميزة المحسوبة، أما في الجدول x المتجهة المميزة المرتبطة بها.

وهي تستدعي الدالة التالية:

 void al_prod_mat_vect(double a[NMAX][NMAX],int n,double x[NMAX],double y[NMAX])

  هذه الدالة يجب أن تعرف في البرنامج الرئيسي.

الثابنة الصحيحة NMAX تساوي البعد القصوي للمصفوفة (+1).

double vp_puissance(double a[NMAX][NMAX],int n,double x[NMAX],double eps)
{
 int i,j,c;
 /* int k; */
 double l,l1;
 double y[NMAX];
 l=0.0;
 /* k=1; */
 do
 {
 c=1;
 l1=l;
 al_prod_mat_vect(a,n,x,y);
 while(y[c]==0)c++;
 l=y[c];
 for(i=1;i<=n;i++)
 x[i]=y[i]/ l;
 /* if((k<=5)||(k/10*10==k)&&(k<=150))
 {
 printf("l(%3d)=%11.5e u(%3d)=(",k,l,k);
 for(i=1;i<=n;i++)
 printf("%11.5e ",x[i]);
 printf(")\n");
 }
 k++; */
 }
 while (fabs(l-l1)>eps);
 return(l);
}

Soyez payé pour partager vos liens!

I'm reading: طريقة الإنكماش

بقلم soufian najim

سفيان، احب أن أضع كل ما أعرف من معلومات حول الحاسوب والتقنيات الجديدة، وخطرت لي فكرة عمل مدونة تضم كل المجالات التعليمية التي أستطيع إفادتكم بها ، فأرجوا ان لاتبخلوا علي أيضا بمتابعتكم لمواضيعي كما ان تعليقاتكم تهمني وتزيد من عطائي لكم إخوتي الكرام وأي استفسار ان موجود وشكرا

قسم : الرئيسية