Giáo trình C++ - Chương 9: Các vấn đề về ma trận

Ch−¬ng 9 : C¸c vÊn ®Ò vÒ ma trËn

§1.§Þnh thøc cña ma trËn

Cho mét ma trËn vu«ng cÊp n.Ta cÇn t×m ®Þnh thøc cña nã.Tr−íc hÕt chóng ta nh¾c

l¹i mét sè tÝnh chÊt quan träng cña ®Þnh thøc:

- nÕu nh©n tÊt c¶ c¸c phÇn tö cña mét hµng (hay cét) víi k th× ®Þnh thøc ®−îc nh©n

víi k

- ®Þnh thøc kh«ng ®æi nÕu ta céng thªm vµo mét hµng tæ hîp tuyÕn tÝnh cña c¸c

hµng cßn l¹i.

Ta sÏ ¸p dông c¸c tÝnh chÊt nµy ®Ó tÝnh ®Þnh thøc cña mét ma trËn cÊp 4 nh− sau(ph−¬ng

ph¸p nµy cã thÓ më réng cho mét ma trËn cÊp n) b»ng ph−¬ng ph¸p trô:

a

a₁₂a₁₃a₁₄

⎛

⎞

11

⎜

⎟

a₂₁a₂₂a₂₃a₂₄

⎜

⎟

A =

a₃₁a₃₂a₃₃a_{34 ⎟}

⎜

⎝

⎟

a₄₁a₄₂a₄₃a_{44 ⎠}

LÊy gi¸ trÞ trô lµ p₁= a₁₁.Ta chia c¸c phÇn tö cña hµng thø nhÊt cho p₁= a₁₁th× ®Þnh thøc sÏ lµ

D/p₁(theo tÝnh chÊt 1) vµ ma trËn cßn l¹i lµ:

′ ′ ′

a₂₁a₂₂a₂₃a₂₄

1

a₁₂a₁₃a₁₄

⎛

⎞

⎜

⎟

⎜

⎟

a₃₁a₃₂a₃₃a_{34 ⎟}

⎜

⎝

⎟

a₄₁a₄₂a₄₃a_{44 ⎠}

LÊy hµng 2 trõ ®i hµng 1 ®· nh©n víi a₂₁,lÊy hµng 3 trõ ®i hµng 1 ®· nh©n víi a₃₁vµ lÊy hµng

4 trõ ®i hµng 1 ®· nh©n víi a₄₁(thay hµng b»ng tæ hîp tuyÕn tÝnh cña c¸c hµng cßn l¹i) th×

®Þnh thøc vÉn lµ D/p₁vµ ma trËn lµ:

′

′ ′

a₁₃a₁₄

1 a

⎛

⎜

⎞

⎟

12

′

0 a₂₂a₂₃a₂₄

⎜

⎟

′

0 a₃₂a₃₃a_{34 ⎟}

⎜

⎝

⎟

′

0 a₄₂a₄₃a_{44 ⎠}

′

LÊy gi¸ trÞ trô lµ p₂= a₂₂.Ta chia c¸c phÇn tö cña hµng thø hai cho p₂th× ®Þnh thøc sÏ lµ

D/(p₁p₂) vµ ma trËn cßn l¹i lµ:

′

1

′ ′

a₁₃a₁₄

1 a

0

⎛

⎜

⎞

⎟

12

′′

′

′′

′

a₂₃a₂₄

⎜

⎟

′

0 a₃₂a₃₃a_{34 ⎟}

⎜

⎝

⎟

′

0 a₄₂a₄₃a_{44 ⎠}

′

LÊy hµng 1 trõ ®i hµng 2 ®· nh©n víia₁₂,lÊy hµng 3 trõ ®i hµng 2 ®· nh©n víi a₃₂vµ lÊy hµng

′

4 trõ ®i hµng 2 ®· nh©n víi a₄₂th× ®Þnh thøc vÉn lµ D/p₁vµ ma trËn lµ:

th× ®Þnh thøc vÉn lµ D/(p₁p₂) vµ ma trËn lµ:

116

′′

a₁₄

′′

1 0 a

⎛

⎜

⎞

⎟

13

′′

0 1 a₂₃a₂₄

⎜

⎟

′′

0 0 a₃₃a_{34 ⎟}

⎜

⎝

⎟

′′

0 0 a₄₃a_{44 ⎠}

TiÕp tôc lÊy hµng 3 råi hµng 4 lµm trô th× ma trËn sÏ lµ:

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

⎛

⎞

⎜

⎟

⎜

⎟

⎜

⎟

⎝

⎠

′ ′′ ′′′

§Þnh thøc cña ma trËn nµy lµ D/(p₁p₂p₃p₄)= D/(a₁₁a₂₂a₃₃a₄₄) =1 nªn ®Þnh thøc cña ma trËn A

lµ D = p₁p₂p₃p₄.

Sau ®©y lµ ch−¬ng tr×nh t×m ®Þnh thøc cña mét ma trËn:

Ch−¬ng tr×nh 9-1

//tinh dinh thuc

#include <conio.h>#include <stdio.h>#include <ctype.h>

#include <stdlib.h>

void main()

{

int i,j,k,n,ok1,ok2,t;

float d,c,e,f,g,h;

float a[50][50];

char tl;

clrscr();

printf("** TINH DINH THUC CAP n **");

printf("\n");

printf("Cho cap cua dinh thuc n = ");

scanf("%d",&n);

printf("Nhap ma tran a\n");

for (i=1;i<=n;i++)

{

printf("Dong %d:\n",i);

for (j=1;j<=n;j++)

{

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i][j]);

}

printf("\n");

}

printf("\n");

printf("Ma tran a ma ban da nhap\n");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

117

printf("%.5f\t",a[i][j]);

printf("\n");

}

printf("\n");

t=1;

flushall();

while (t)

{

printf("Co sua ma tran a khong(c/k)?");

scanf("%c",&tl);

if (toupper(tl)=='C')

{

printf("Cho chi so hang can sua : ");

scanf("%d",&i);

printf("Cho chi so cot can sua : ");

scanf("%d",&j);

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i,j]);

}

if (toupper(tl)=='K')

t=0;

}

printf("Ma tran a ban dau\n");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

printf("%.5f\t",a[i][j]);

printf("\n");

}

printf("\n");

d=1;

i=1;

ok2=1;

while ((ok2)&&(i<=n))

{

if (a[i][i]==0)

{

ok1=1;

k=k+1;

while ((ok1)&&(k<=n))

if (a[k,i]!=0)

{

for (j=i;j<=n;j++)

{

c=a[i][j];

a[i][j]=a[k][j];

a[k][j]=c;

}

d=-d;

118

ok1=0;

}

else

k=k+1;

if (k>n)

{

printf("\n");

printf("** MA TRAN SUY BIEN **");

ok2=0;

d=0;

}

if (a[i][i]!=0)

{

c=a[i][i];

for (j=i+1;j<=n;j++)

a[i][j]=a[i][j]/c;

for (k=i+1;k<=n;k++)

{

c=a[k][i];

for (j=i+1;j<=n;j++)

a[k][j]=a[k][j]-a[i][j]*c;

}

i=i+1;

}

if (ok2)

{

for (i=1;i<=n;i++)

d=d*a[i][i];

printf("\n");

printf("** GIA TRI DINH THUC D **");

printf("\n");

printf("%.3f",d);

}

getch();

}

§2.NghÞch ®¶o ma trËn

Gäi A^-1lµ ma trËn nghÞch ®¶o cña mét ma trËn A bËc n ta cã AA^-1= E.(trong biÓu

thøc nµy E lµ mét ma trËn vu«ng cã c¸c phÇn tö trªn ®−êng chÐo chÝnh b»ng 1). D¹ng cña

ma trËn E,vÝ dô cÊp 4,lµ:

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

⎛

⎜

⎞

⎟

E =

⎜

⎟

⎜

⎝

⎟

⎠

119

Ph−¬ng ph¸p lo¹i trõ ®Ó nhËn ®−îc ma trËn nghÞch ®¶o A^-1®−îc thùc hiÖn qua nhiÒu

giai ®o¹n (n),mçi mét giai ®o¹n gåm hai b−íc.§èi víi giai ®o¹n thø k:

- chuÈn ho¸ phÇn tö a_kkb»ng c¸ch nh©n hµng víi nghÞch ®¶o cña nã

- lµm cho b»ng kh«ng c¸c phÇn tö phÝa trªn vµ phÝa d−íi ®−êng chÐo cho ®Õn cét thø

k.Khi k = n th× A^(k)sÏ trë thµnh ma trËn ®¬n vÞ vµ E trë thµnh A^-1

VÝ dô: TÝnh ma trËn nghÞch ®¶o cña ma trËn

2 1 1

⎛

⎞

⎟

⎜

A = 1 2 1

⎜

⎟

1 1 2

⎝

⎠

Ta viÕt l¹i ma trËn A vµ ma trËn ®¬n vÞ t−¬ng øng víi nã

2 1 1

1 0 0

⎛

⎞

⎟

⎛

⎞

⎟

⎜

A = 1 2 1

E = 0 1 0

⎜

⎟

⎜

⎟

1 1 2

0 0 1

⎝

⎠

⎝

⎠

Giai ®o¹n 1: B−íc a: Nh©n hµng 1 víi 1/a₁₁,nghÜa lµ a^,_1j= a_1j/a₁₁®èi víi dßng thø nhÊt,a^,_ij=

a_ij®èi víi c¸c dßng kh¸c

1 1 2 1 2

1 2 0 0

⎛

⎞

⎟

⎛

⎞

⎟

⎜

A = 1

2

1

2

E = 0 1 0

⎜

⎟

⎠

⎜

⎟

⎠

1

⎝

0

0 1

⎝

B−íc b: Trõ hµng 3 vµ hµng 2 cho hµng 1,nghÜa lµ a⁽¹⁾_1j= a_ij- a_i1a_ij®èi víi i ≠

1.

1 1 2 1 2

1 2 0 0

⎛

⎞

⎟

⎛

⎞

⎟

⎜

A = 0 3 2 1 2

E = −1 2 1 0

⎜

⎟

⎜

⎟

0 1 2 3 2

−1 2 0 1

⎝

⎠

⎝

⎠

Giai ®o¹n 2: B−íc a: LÊy hµng 2 lµm chuÈn,nh©n hµng 2 víi 2/3,®Ó nguyªn c¸c hµng kh¸c

1 1 2 1 2

1 2

0

⎛

⎞

⎛

⎞

⎜

⎟

⎜

⎟

A = 0

1

1 3

E = −1 3 2 3 0

⎜

⎟

⎠

⎜

⎟

⎠

0 1 2 3 2

−1 2

0

1

⎝

B−íc b: LÊy hµng 1 trõ ®i hµng 2 nh©n 1/2 vµ lÊy hµng 3 trõ ®i hµng 2 nh©n

1/2

1 0 1 3

2 3 −1 3 0

⎛

⎞

⎟

⎛

⎞

⎟

⎜

A = 0 1 1 3

E = −1 3 2 3

0

⎜

⎟

⎜

⎟

0 0 4 3

−1 3 −1 3 1

⎝

⎠

⎝

⎠

Giai ®o¹n 3: B−íc a: LÊy hµng 3 lµm chuÈn,nh©n hµng 3 víi 3/4,®Ó nguyªn c¸c hµng kh¸c

1 0 1 3

2 3 −1 3

0

⎛

⎞

⎛

⎞

⎜

⎟

⎜

⎟

A = 0 1 1 3

E = −1 3 2 3

⎜

⎟

⎠

⎜

⎟

⎠

0 0

1

−1 4 −1 4 3 4

⎝

B−íc b: LÊy hµng 1 trõ ®i hµng 3 nh©n 1/3 vµ lÊy hµng 2 trõ ®i hµng 3 nh©n

1/3

3 4 −1 4 −1 4

⎛

⎞

⎟

1 0 0

⎛

⎞

⎟

⎜

A = 0 1 0

E = −1 4 3 4 −1 4

⎜

⎟

⎠

⎜

⎟

0 0 1

−1 4 −1 4 3 4

⎝

⎠

⎝

Nh− vËy A^-1lµ:

120

3 4 −1 4 −1 4

−1 4 3 4 −1 4

−1 4 −1 4 3 4

⎛

⎜

⎞

⎟

A⁻¹

=

⎜

⎝

⎟

⎠

¸p dông ph−¬ng ph¸p nµy chóng ta cã ch−¬ng tr×nh sau:

Ch−¬ng tr×nh 9-2

#include <conio.h>#include <stdio.h>#include <math.h>#include <stdlib.h>#include

<ctype.h>void main() { int i,j,k,n,t,t1;float c,a[50][50],b[50][50]; char tl;

printf(" **MA TRAN NGHICH DAO** \n");

clrscr();

printf("Cho bac cua ma tran n = ");

scanf("%d",&n);

printf("Vao ma tran ban dau a\n");

for (i=1;i<=n;i++)

{

printf("Vao hang thu %d :\n",i);

for (j=1;j<=n;j++)

{

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i][j]);

}

printf("\n");

}

printf("\n");

printf("Ma tran ban da nhap\n");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

printf("%.5f\t",a[i][j]);

printf("\n");

}

t=1;

flushall();

while (t)

{

printf("\nCo sua ma tran khong(c/k)?");

scanf("%c",&tl);

if(toupper(tl)=='C')

{

printf("Cho chi so hang can sua : ");

scanf("%d",&i);

printf("Cho chi so cot can sua : ");

scanf("%d",&j);

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i][j]);

}

if (toupper(tl)=='K')

t=0;

}

printf("\nMa tran ban dau\n");

121

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

printf("%.5f\t",a[i][j]);

printf("\n");

}

printf("\n");

for (i=1;i<=n;i++)

for (j=n+1;j<=2*n;j++)

{

if (j==i+n)

a[i][j]=1;

else

a[i][j]=0;

}

i=1;

t1=1;

while (t1&&(i<=n))

{

if (a[i][i]==0)

{

t=1;

k=i+1;

while (t&&(k<=n))

if (a[k][i]!=0)

{

for (j=1;j<=2*n;j++)

{

c=a[i][j];

a[i][j]=a[k][j];

a[k][j]=c;

}

t=0;

}

else

k=k+1;

if (k==n+1)

{

if (a[i][k-1]==0)

{

printf("MA TRAN SUY BIEN\n ");

t1=0;

}

if (a[i][i]!=0)

{

c=a[i][i];

for (j=i;j<=2*n;j++)

122

a[i][j]=a[i][j]/c;

}

for (k=1;k<=n;k++)

{

if (k!=i)

{

c=a[k][i];

for (j=i;j<=2*n;j++)

a[k][j]=a[k][j]-a[i][j]*c;

}

i=i+1;

}

if (t1)

{

printf("\n");

printf("\nMA TRAN KET QUA\n");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=n+1;j<=2*n;j++)

printf("%.4f\t\t",a[i][j]);

printf("\n");

}

printf("\n");

}

getch();

}

Dïng ch−¬ng tr×nh tÝnh nghÞch ®¶o cña ma trËn:

9 9 8

−1

2

−10

9

−1

9

− 9

⎛

⎞

⎛

⎞

⎟

⎜

⎟

⎜

9 8 7 cho ta kÕt qu¶

2

⎜

⎝

⎟

⎜

⎝

⎟

8 7 6

−1

⎠

§3.TÝch hai ma trËn

Gi¶ sö ta cã ma trËn A_mnvµ ma trËn B_np.TÝch cña A_mnvµ B_nplµ ma trËn C_mptrong ®ã

n

mçi phÇn tö cña C_mplµ:

c = a b

ij ik kj

∑

k=1

Ch−¬ng tr×nh d−íi ®©y thùc hiÖn nh©n hai ma trËn víi nhau.

Ch−¬ng tr×nh 9-3

#include <conio.h>#include <stdio.h>#include <math.h>#include <stdlib.h>#include

<ctype.h>

#define max 50

void main()

123

{

int n,l,m,i,j,k,t;

float a[max][max],b[max][max],c[max][max];

char tl;

clrscr();

printf("Cho so hang cua ma tran a : ");

scanf("%d",&n);

printf("Cho so cot cua ma tran a : ");

scanf("%d",&l);

printf("Cho so cot cua ma tran b : ");

scanf("%d",&m);

printf("\nNHAP MA TRAN A\n");

for (i=1;i<=n;i++)

for (j=1;j<=l;j++)

{

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i][j]);

}

printf("\n");

printf("Ma tran a ma ban da nhap\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=l;j++)

printf("%10.5f",a[i][j]);

printf("\n");

}

flushall();

t=1;

while (t)

{

printf("Co sua ma tran khong(c/k)?");

scanf("%c",&tl);

if (toupper(tl)=='C')

{

printf("Cho chi so hang can sua : ");

scanf("%d",&i);

printf("Cho chi so cot can sua : ");

scanf("%d",&j);

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i][j]);

}

if (toupper(tl)=='K')

t=0;

}

printf("Ma tran a ban dau");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=l;j++)

124

printf("%10.5f",a[i][j]);

printf("\n");

}

printf("\n");

printf("NHAP MA TRAN B\n");

for (i=1;i<=l;i++)

for (j=1;j<=m;j++)

{

printf("b[%d][%d] = ",i,j);

scanf("%f",&b[i][j]);

}

printf("\n");

printf("Ma tran b ban da nhap\n");

for (i=1;i<=l;i++)

{

for (j=1;j<=m;j++)

printf("%10.5f",b[i][j]);

printf("\n");

}

flushall();

t=1;

while (t)

{

printf("Co sua ma tran khong(c/k)?");

scanf("%c",&tl);

if (toupper(tl)=='C')

{

printf("Cho chi so hang can sua : ");

scanf("%d",&i);

printf("Cho chi so cot can sua : ");

scanf("%d",&j);

printf("b[%d][%d] = ",i,j);

scanf("%f",&b[i][j]);

}

if (toupper(tl)=='K')

t=0;

}

printf("Ma tran b ban dau");

printf("\n");

for (i=1;i<=l;i++)

{

for (j=1;j<=m;j++)

printf("%10.5f",b[i][j]);

printf("\n");

}

printf("\n");

for (i=1;i<=n;i++)

for (j=1;j<=m;j++)

{

125

c[i][j]=0;

for (k=1;k<=l;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

}

printf("Ma tran tich c :\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=m;j++)

printf("%10.5f",c[i][j]);

printf("\n");

}

getch();

}

Dïng ch−¬ng tr×nh tÝnh tÝnh hai ma trËn ta nhËn ®−îc kÕt qu¶

2

1

5

8

1

0

−1

⎛

⎞

⎛

⎞

⎜

⎟

⎜

⎟

−1 3

1

2

− 2

3

−14 11

⎛

⎜

⎝

⎞

⎟

⎠

×

=

⎜

⎟

⎜

⎟

1

5

0

3

3 − 4

2

− 2

⎜

⎝

⎟

⎠

⎜

⎝

⎟

⎠

14 − 2 −1

§4.Gi¸ trÞ riªng vµ vec t¬ riªng cña ma trËn

1.Kh¸i niÖm chung: Trong nghiªn lÝ thuyÕt vµ øng dông,ta gÆp bµi to¸n vÒ ma trËn cÊp

n.Cho mét ma trËn A cÊp n,gi¸ trÞ λ ®−îc gäi lµ gi¸ trÞ riªng vµ vect¬ X ®−îc gäi lµ vect¬

riªng cña ma trËn A nÕu:

AX = λX

(1)

Vect¬ riªng ph¶i lµ vect¬ kh¸c kh«ng.T−¬ng øng víi mét gi¸ trÞ riªng cã v« sè vect¬

riªng.NÕu X lµ mét vÐc t¬ riªng t−¬ng øng víi gi¸ trÞ riªng λ th× cX còng lµ vec t− riªnh øng

víi λ.Cã nhiÒu thuËt to¸n t×m gi¸ trÞ riªng vµ vect¬ riªng cña mét ma trËn.Gi¶ sö ta cã ma

trËn A,gäi E lµ ma trËn ®¬n vÞ th× theo (1) ta cã:

(A-λE)X = 0

(2)

vµ (A - λE) lµ ma trËn cã d¹ng:

⎞

⎟

^⎛_⎜a₁₁

⁻λ a₁₂

a

....

1n

(3)

^⎜a₂₁a₂₂⁻λ

a

....

⎟

2n

^⎜_⎜.......

⎜

_⎝a_n1a_n2

a

⁻λ ^⎟_⎠

....

nn

Nh− vËy do (2) lµ hÖ ph−¬ng tr×nh tuyÕn tÝnh thuÇn nhÊt nªn ®iÒu kiÖn cÇn vµ ®ñ ®Ó λ

lµ gi¸ trÞ riªng cña ma trËn trªn lµ ®Þnh thøc cña nã b»ng kh«ng:

det(A - λE) = 0

(4)

Ph−¬ng tr×nh (4) ®−îc gäi lµ ph−¬ng tr×nh ®Æc tr−ng cña ma trËn A.§Þnh thøc det(A - λE)

®−îc gäi lµ ®Þnh thøc ®Æc tr−ng cña ma trËn A.§Þnh thøc P_A(λ) cña ma trËn trªn ®−îc gäi lµ

®a thøc ®Æc tr−ng cña ma trËn vu«ng A.

VÝ dô t×m vec t¬ riªng vµ trÞ riªng cña ma trËn:

3

2

1

− 2

−3

−1

0

⎛

⎞

⎜

⎟

⎜

⎝

⎟

⎠

Tr−íc hÕt ta tÝnh ®a thøc ®Æc tr−ng cña ma trËn A:

126

⎞

⎟

^⎛_⎜3−λ

^⎜_⎜3

1

−3

2

⎟

+

(4−λ) (λ 4)

(λ)=

P_A

1−λ

−1 =

^⎜_⎝2

−2

−λ ^⎟_⎠

NghiÖm cña P_A(λ) = 0 lµ λ₁= 4,λ₂= 2j vµ λ₃= -2j.V× tr−êng c¬ së lµ sè thùc nªn ta chØ lÊy λ

= 4.§Ó t×m vec t¬ riªng t−¬ng øng víi λ = 4 ta gi¶i hÖ

⎞

^⎛_⎜3−λ

1

−3

−1

⎛ξ₁⎞

⎟

⎜ ⎟

ξ₂

^⎜_⎜3

1−λ

⁼0

×

⎜ ⎟

^⎜_⎝2

−2

−λ ^⎟_⎠

ξ

⎝ ³⎠

ta nhËn ®−îc c¸c gi¸ trÞ cña ξ,chóng t¹o thµnh vec t¬ riªng øng víi λ.

Nh− vËy khi khai triÓn ®Þnh thøc ta cã mét ®a thøc bËc n cã d¹ng:

P_n(λ) = λⁿ- p₁λ^n-1- p₂λ^n-2- …- p_n= 0

Muèn x¸c ®Þnh c¸c hÖ sè cña ®a thøc ®Æc tÝnh nµy ta dïng ph−¬ng ph¸p Fadeev-Leverrier.Ta

xÐt ma trËn A:

a

a₁₂⋅⋅⋅ a_1n

⎛

⎞

11

⎜

⎟

a₂₁a₂₂⋅⋅⋅ a_2n

⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅ ⋅⋅⋅

a_n1a_n2⋅⋅⋅ a_{nn ⎠}

⎜

⎟

A =

⎜

⎟

⎝

Ta gäi vÕt cña ma trËn A lµ sè:

vet(A)= a₁₁+ a₂₂+...+ a_nn

Khi ®ã tham sè p_icña P_n(λ) ®−îc c¸c ®Þnh nh− sau:

p₁= vet(B₁) víi

p₂= (1/2)vet(B₂)

p₃= (1/3)vet(B₃)

......

B₁= A

víi

B₂= A(B₁-p₁E)

B₃= A(B₂-p₂E)

Ch−¬ng tr×nh tÝnh c¸c hÖ sè p_inh− sau:

Ch−¬ng tr×nh 9-4

// Faddeev_Leverrier;

#include <stdio.h>

#include <conio.h>

#include <ctype.h>

#define max 50

void main()

{

int i,j,k,m,n,k1,t;

float vet,c1,d;

char tl;

float p[max];

float a[max][max],b[max][max],c[max][max],b1[max][max];

clrscr();

printf("Cho bac cua ma tran n = ");

scanf("%d",&n);

printf("Cho cac phan tu cua ma tran a : \n");

127

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

printf("a[%d][%d] = ",i,j );

scanf("%f",&a[i][j]);

}

printf("\n");

clrscr();

printf("Ma tran ban da nhap");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

printf("%10.5f",a[i][j]);

printf("\n");

}

t=1;

flushall();

while (t)

{

printf("\n");

printf("Co sua ma tran khong(c/k)?");

scanf("%c",&tl);

if (toupper(tl)=='C')

{

printf("Cho chi so hang can sua : ");

scanf("%d",&i);

printf("Cho chi so cot can sua : ");

scanf("%d",&j);

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i][j]);

flushall();

}

if (toupper(tl)=='K')

t=0;

}

printf("Ma tran ban dau");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

printf("%10.5f",a[i][j]);

printf("\n");

}

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

b[i][j]=a[i][j];

for (k=1;k<=n-1;k++)

{

vet=0.0;

128

for (i=1;i<=n;i++)

vet+=b[i][i];

p[k]=vet/k;

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

if (j!=i)

c[i][j]=b[i][j];

if (j==i)

c[i][j]=b[i][j]-p[k];

}

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

b[i][j]=0.0;

for (k1=1;k1<=n;k1++)

b[i][j]+=a[i][k1]*c[k1][j];

}

vet=0.0;

for (i=1;i<=n;i++)

vet+=b[i][i];

p[n]=vet/n;

printf("\n");

printf("Cac he so cua da thuc dac trung\n");

printf("\n");

d=1.0;

printf("%6.2f",d);

for (i=1;i<=n;i++)

{

c1=-p[i];

printf("%5c%6.2f",' ',c1);

}

getch();

}

2.Ph−¬ng ph¸p Mises: ThuËt to¸n Mises t×m gi¸ trÞ riªng lín nhÊt cña mét ma trËn A. NÕu

ma trËn A lµ thùc vµ vµ mçi trÞ riªng béi k cã ®ñ k vec t¬ riªng ®éc lËp tuyÕn tÝnh th× viÖc

tÝnh to¸n sÏ cho ta gi¸ trÞ riªng lín nhÊt.

Mét vect¬ V bÊt k× cã thÓ ®−îc viÕt d−íi d¹ng:

n

V = v X + v X + ⋅⋅⋅ + v X = v X

i

(5)

∑

1

2

n

i

i=1

Trong ®ã X₁,X₂,..,X_nlµ c¸c vec t¬ riªng t−¬ng øng víi c¸c gi¸ trÞ riªng λ_1,λ₂,λ₃,..,λ_n

vµ v₁,v₂,v₃,...,v_nlµ c¸c h»ng sè.

Khi nh©n A víi V ta cã:

AV = Av₁X₁+ Av₂X₂+....+ Av_nX_n

do:

VËy nªn:

Av₁X₁= v₁AX₁= v₁λ₁X₁; Av₂X₂= v₂AX₂= v₂λ₂X₂v.v.

AV = v₁λ₁X₁+ v₂λ₂X₂+...+ v_nλ_nX_n

129

n

=

∑

AV

v_iA_iX_iv_iλ_iX_i

i=1

L¹i nh©n biÓu thøc trªn víi A ta cã:

A²V = v₁λ₁AX₁+ v₂λ₂AX₂+...+ v_nλ_nAX_n

= v₁λ²X₁+ v₂λ₂X₂+...+ v_nλ_nX_n

2

1

vµ tiÕp ®Õn lÇn thø p ta cã:

n

p

^pV

v_iλ_iX_iv₁λ₁X₁v₁λ₂X₂^{+ ⋅⋅+}v_nλ_nX_n

=

+

∑

A

i=1

LÊy λ^p₁lµm thõa sè chung ta cã:

p

⎡

⎤

⎥

⎛

⎞

⎛

⎞

⎛

⎞

λ₂

λ₃

λ_n

p

⎢

⎜

⎟

⎜

⎟

⎜

⎟

A V = λ₁v₁X₁+ v₂

X₂+ v₃

X₃+ ⋅⋅⋅ + v_n

X_n

λ_{1 ⎠}

⎢

⎣

⎥

⎦

⎝

T−¬ng tù ta cã:

p+1

⎡

⎤

⎛

⎞

⎛

⎞

⎛

⎞

λ₂

λ₃

λ_n

A^p+1V = λ^p₁⁺¹v₁X₁+ v₂

X₂+ v₃

X₃+ ⋅⋅⋅ + v_n

X_n

⎢

⎥

⎜

⎟

⎜

⎟

⎜

⎟

λ_{1 ⎠}

⎢

⎥

⎦

⎝

⎣

Khi p rÊt lín,v× λ₁> λ₂> λ₃>,...,λ_nnªn:

⎛

⎞

λ_i

⎜

⎟

→ 0 khi p → ∞

λ_{1 ⎠}

⎝

lim A^pV = λ^p₁v₁X₁

Do ®ã:

(6)

p→∞

lim A^p+1V = λ^p₁⁺¹v₁X₁

p→∞

nghÜa lµ khi p ®ñ lín th×:

A^pV = λ^p₁v₁X₁

A^p+1V = λ^p₁⁺¹v₁X₁

A^p+1V = λ₁A^pV

do ®ã:

A

(

A^pV

)

= λ₁A^pV

hay:

p

Nh− vËy

lµ vÐc t¬ riªng cña A øng víi λ₁cßn gi¸ trÞ riªng λ₁sÏ lµ:

A V

A^p+1

V

lim

= λ₁

A^pV

p→∞

Trong thùc tÕ ®Ó tr¸nh v−ît qu¸ dung l−îng bé nhí khi λ₁kh¸ lín,c¸c vect¬ V_k®−îc

chuÈn ho¸ sau mçi b−íc b»ng c¸ch chia c¸c phÇn tö cña nã cho phÇn tö lín nhÊt m_kvµ nhËn

®−îc vect¬ V^’_k

Nh− vËy c¸c b−íc tÝnh sÏ lµ:

- cho mét vec t¬ V bÊt k× (cã thÓ lµ V = { 1,1,1,...,1}^T)

- tÝnh V₁= AV vµ nhËn ®−îc phÇn tö lín nhÊt lµ m_1jtõ ®ã tÝnh tiÕp V^′₁= V₁/m_1j

Mét c¸ch tæng qu¸t,t¹i lÇn lÆp thø p ta nhËn ®−îc vect¬ V_pvµ phÇn tö lín nhÊt m_pjth×

V^’_p= V_p/ m_pj.

′

- tÝnh V_p+1= AV_pvíi v_p+1,jlµ phÇn tö thø j cña V_p+1.Ta cã:

′

lim V = X

⎧

⎪

p

1

p→∞

⎨

lim v_p+1,j= λ₁

⎪

⎩

p→∞

VÝ dô: T×m gi¸ trÞ riªng lín nhÊt vµ vec t¬ riªng t−¬ng øng cña ma trËn:

130

17

8

24

13

10

30

20

8

17

7

⎛

⎜

⎞

⎟

A =

⎜

⎟

2

6

⎜

⎝

⎟

⎠

− 23 − 43 − 54 − 26

Chän V= {1,1,1,1}^Tta tÝnh ®−îc

V

V₁= AV

V’₁

V₂=

V’₂

AV’₁

1

88

48

26

-0.6027

-0.3288

-0.1781

1

-6.4801

-5.6580

0.0818

11.6179

-0.5578

-0.4870

0.0070

1

-146

λ

V₃=

AV’₂

V’₃

V₄= AV’₃

V’₄

V₅=

AV’₄

-3.9594

-3.6526

0.0707

7.3902

-0.5358

-0.4942

0.0096

1

-3.6823

-3.5196

0.0630

7.0573

-0.5218

-0.4987

0.0089

1

-3.5718

-3.4791

0.0408

6.9638

V’₅

V₆=

AV’₅

-3.5341

V’₆

V₇= AV’₆

-3.5173

-3.4868

V’₇

-

-0.5075

-0.4999

-0.5043

-0.5000

0.5129

-

-3.4809

0.4996

0.0059

1

0.0250

6.9634

0.0036

1

0.0147

6.9742

0.0021

1

λ

Dïng thuËt to¸n trªn ta cã ch−¬ng tr×nh sau:

Ch−¬ng tr×nh 9-5

#include <conio.h>#include <stdio.h>#include <math.h>#include <stdlib.h>#include

<ctype.h>#define max 50void main() { int i,j,k,n,t; char tl;

float a[max][max];

float

t0,t1,epsi,s;

float x0[max],x1[max];

clrscr();

printf("Phuong phap lap luy thua tim tri rieng lon nhat\n");

printf("Cho so hang va cot cua ma tran n = ");

scanf("%d",&n);

printf("Cho cac phan tu cua ma tran a : \n");

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

131

{

}

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i][j]);

printf("\n");

printf("Ma tran ban da nhap\n");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

printf("%15.5f",a[i][j]);

printf("\n");

}

flushall();

t=1;

while (t)

{

printf("\nCo sua ma tran khong(c/k)?");

scanf("%c",&tl);

if (toupper(tl)=='C')

{

printf("Cho chi so hang can sua : ");

scanf("%d",&i);

printf("Cho chi so cot can sua : ");

scanf("%d",&j);

printf("a[%d][%d] = ",i,j);

scanf("%f",&a[i][j]);

}

if (toupper(tl)=='K')

t=0;

}

epsi=1e-5;

printf("\nMa tran ban dau\n");

printf("\n");

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

printf("%15.5f",a[i][j]);

printf("\n");

}

printf("\n");

for (i=1;i<=n;i++)

x0[i]=1;

k=1;

t=0;

t1=0;

do

{

t0=t1;

for (i=1;i<=n;i++)

132

{

x1[i]=0;

for (j=1;j<=n;j++)

x1[i]=x1[i]+a[i][j]*x0[j];

}

s=0;

j=0;

for (i=1;i<=n;i++)

if (s<fabs(x1[i]))

{

j=i;

s=fabs(x1[i]);

}

t1=x1[j];

for (i=1;i<=n;i++)

x1[i]=x1[i]/t1;

if (fabs(t1-t0)<epsi)

{

printf("Da thuc hien %d buoc lap\n",k);

printf("Gia tri rieng lon nhat Vmax = %15.5f\n",t1);

printf("Vec to rieng tuong ung\n");

for (i=1;i<=n;i++)

printf("%.5f\n",x1[i]);

t=1;

}

if (fabs(t1-t0)>epsi)

{

for (i=1;i<=n;i++)

x0[i]=x1[i];

k=k+1;

}

if (k>max)

t=1;

}

while(t==0);

getch();

}

Dïng ch−¬ng tr×nh nµy tÝnh gÝa trÞ riªng vµ vec t¬ riªng cña ma trËn:

2

9

− 8

−1

0

6

− 3

⎛

⎞

⎜

⎟

4

⎜

⎝

⎟

⎠

0

ta nhËn ®−îc gi¸ trÞ riªng lµ 3.0000 vµ vec t¬ riªng lµ x = { -0.75 ; 0.75 ; 1 }^T

lòy thõa) chØ cho phÐp t×m gi¸ trÞ riªng lín nhÊt vµ vec t¬ riªng t−¬ng øng cña ma trËn.§Ó

x¸c ®Þnh c¸c gi¸ trÞ riªng kh¸c,ma trËn A ®−îc biÕn ®æi thµnh mét ma trËn kh¸c A₁mµ c¸c

ph−¬ng ph¸p biÕn ®æi ma trËn:

133

Gi¶ sö X₁lµ vec t¬ riªng cña ma trËn A t−¬ng øng víi gi¸ trÞ riªng λ₁vµ W₁lµ vec t¬

riªng cña ma trËn A^Tt−¬ng øng víi gi¸ trÞ riªng λ₁.Tõ ®Þnh nghÜa AX₁= λ₁X₁ta viÕt:

(A - λE)X₁= 0

Ta t¹o ma trËn A₁d¹ng:

(7)

X₁W₁^T

λ₁

=

−

A₁A

W₁^TX₁

T

(7) víi X₁vµ chý ý ®Õn tÝnh kÕt hîp cña tÝch c¸c ma trËn ta cã:

X₁W₁^TX₁

λ₁

=

−

A₁X₁AX₁

W₁^TX₁

(8)

W₁^TX₁

−

⁼AX₁λ₁X

⁼AX₁λ₁X₁

¹W₁^TX₁

−

⁼0

A₁chÊp nhËn gi¸ trÞ riªng b»ng kh«ng.

X₁W₁^TX₂

λ₁

=

−

(9)

A₁X₂AX₂

W₁^TX₁

W₁^TX₂

−

⁼AX₂λ₁X

¹W₁^TX₁

Theo ®Þnh nghÜa v× W₁lµ vect¬ riªng cña A^Tnªn:

λ₁W₁=A^TW₁

(10)

MÆt kh¸c do:

(AX)^T=X^TA^Tvµ (A^T)^T= A

Nªn khi chuyÓn vÞ (10) ta nhËn ®−îc:

(A^TW₁)^T= λ₁W^T

1

Hay:

T

W₁A = λ₁W₁

(11)

T

λ₁W₁X₂= W₁AX₂

vµ do ®Þnh nghÜa:

AX₂= λ₂X₂

nªn:

T

λ₁W₁X₂= W₁λ₂X₂

vËy th×:

T

(λ₁- λ₂) W₁X₂= 0

khi λ₁≠ λ₂th×:

T

W₁X₂= 0

(12)

Cuèi cïng thay (12) vµo (9) ta cã:

A₁X₂= AX₂= λ₂X₂

Nh− vËy λ₂lµ gi¸ trÞ riªng lín nhÊt cña ma trËn A₁vµ nh− vËy cã thÓ ¸p dông thuËt

to¸n nµy ®Ó t×m c¸c gi¸ trÞ riªng cßn l¹i cña ma trËn.C¸c b−íc tÝnh to¸n nh− sau

- khi ®· cã λ₁vµ X₁ta t×m W₁lµ vec t¬ riªng cña A^Tøng víi gi¸ trÞ riªng λ₁(vÝ dô t×m

W₁b»ng c¸ch gi¶i ph−¬ng tr×nh (A^T-λ₁E)W₁= 0).Tõ ®ã tÝnh ma trËn A₁₂theo (7).

- t×m gi¸ trÞ riªng vµ vec t¬ riªng cña A₁b»ng c¸ch lÆp c«ng suÊt vµ cø thÕ tiÕp tôc vµ

xuèng thang (n-1) lÇn ta t×m ®ñ n gi¸ trÞ riªng cña ma trËn A.

VÝ dô: T×m gi¸ trÞ riªng vµ vect¬ riªng cña ma trËn sau:

134

17

8

24

13

10

30

20

8

17

7

⎛

⎜

⎞

⎟

A =

⎜

⎟

2

6

⎜

⎟

− 23 − 43 − 54 − 26

⎝

⎠

Ta ®· t×m ®−îc gi¸ trÞ riªng lín nhÊt λ₁= 7 vµ mét vect¬ riªng t−¬ng øng:

X₁= { 1,1,0,-2}^T.

Ma trËn A^Tcã d¹ng:

17

8

2

−23

⎛

⎞

⎟

⎜

24 13 10 −43

A^T

=

⎜

⎟

30 20

17

8

6

−54

−26

⎜

⎟

7

⎝

⎠

vµ theo ph−¬ng tr×nh A^T-λ₁E)W₁= 0 ta t×m ®−îc vect¬ W₁= {293,695,746,434}^T

Ta lËp ma trËn míi A₁theo (7):

293

0

695

0

746

0

434

0

⎛

⎞

⎟

X₁W₁^T

W₁^TX₁

⎜

7

λ₁

=

⎜

⎟

120

⎜

⎝

⎟

⎠

− 586 −1390 −1492 − 868

vµ:

−0.0917 −16.5417 −13.5167 −8.3167

−9.0917 −27.5417 −23.5167 −18.3167

⎛

⎜

⎞

⎟

=

A₁

⎜

⎟

2

10

8

6

⎜

⎟

11.1833 38.0833

33.0333 24.6333

⎝

⎠

Tõ ma trËn A₁ta t×m tiÕp ®−îc λ₂theo phÐp lÆp luü thõa vµ sau ®ã l¹i t×m ma trËn A₃vµ t×m

gi¸ trÞ riªng t−¬ng øng.

Ch−¬ng tr×nh lÆp t×m c¸c gi¸ trÞ riªng vµ vec t¬ riªng cña ma trËn nh− sau:

Ch−¬ng tr×nh 9-6

#include <conio.h>

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <ctype.h>

#define max 50

void main()

{

float a[max][max],vv[max][max],at[max][max];

float x[max],y[max],vd[max];

int i,j,k,n,l,t;

float vp,v1,z,epsi,va,ps;

char tl;

clrscr();

epsi=0.000001;

printf("Cho bac cua ma tran n = ");

scanf("%d",&n);

printf("Cho cac phan tu cua ma tran a : \n");

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

135