Bài giảng Phương pháp tính - Chương 4: Giải hệ phương trình đại số tuyến tính
CHƯƠNG 4 : GIẢI HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN
TÍNH
§1. PHƯƠNG PHÁP GAUSS
Có nhiều phương pháp để giải một hệ phương trình tuyến tính dạng AX
= B. Phương pháp giải sẽ đơn giản hơn nếu ma trận A có dạng tam giác nghĩa
là có dạng :
a
a
0
a22
0
0
a
a12
a
a
11
11
13
hay
0 a22
0
23
21
a31 a32 a33
0 a33
Trong trường hợp đầu tiên, ma trận được gọi là ma trận tam giác dưới
và trường hợp thứ hai ma trận được gọi là ma trận tam giác trên. Phương
trình tương ứng với ma trận tam giác dưới có dạng tường minh là :
a x 0x 0x b
11
1
2
3
1
a x a x 0x b
21
1
22
2
3
2
a31x1 a32x2 a33 x3 b3
Với phương trình dạng này chúng ta sẽ giải phương trình từ trên xuống.
Chương trình giải phương trình ma trận tam giác dưới là :
Chương trình 4-1
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define max 10
void main()
{
float a[max][max];
float b[max],x[max];
int i,j,k,n,t;
float s,c;
char tl;
clrscr();
83
printf("Cho so phuong trinh 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++)
{
printf("a[%d][%d] = ",i,j);
scanf("%f",&a[i][j]);
}
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++)
printf("%15.5f",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");
84
printf("\n");
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
printf("%15.5f",a[i][j]);
printf("\n");
}
printf("\n");
printf("Cho cac phan tu cua ma tran b\n");
for (i=1;i<=n;i++)
{
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
printf("\n");
printf("Ma tran b ma ban da nhap");
printf("\n");
for (i=1;i<=n;i++)
printf("b[%d] = %10.5f\n",i,b[i]);
printf("\n");
flushall();
t=1;
while (t)
{
printf("Co sua ma tran b khong(c/k)?");
scanf("%c",&tl);
if (toupper(tl)=='C')
{
printf("Cho chi so hang can sua : ");
scanf("%d",&i);
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
if (toupper(tl)=='K')
t=0;
}
printf("\n");
printf("Ma tran b ban dau");
85
printf("\n");
for (i=1;i<=n;i++)
printf("%15.5f\n",b[i]);
{
if (a[1][1]==0)
if (b[1]!=0)
printf("He da cho vo nghiem\n");
else
{
printf("He da cho co vo so nghiem");
x[n]=c;
}
else
x[1]=b[1]/a[1][1];
for (i=2;i<=n;i++)
{
s=0;
for (k=1;k<=i-1;k++)
s=s+a[i][k]*x[k];
x[i]=(b[i]-s)/a[i][i];
}
printf("\n");
printf("Nghiem cua he da cho la");
printf("\n");
for (i=1;i<=n;i++)
printf("x[%d] = %10.5f\n",i,x[i]);
getch();
}
}
Phương trình tương ứng với ma trận tam giác trên có dạng tường minh là :
a x a x a x b
11
1
12
2
13
3
1
0x a x a x b
1
22
2
23
3
2
0x1 0x2 a33 x3 b3
Với phương trình này chúng ta giải từ dưới lên.
Chương trình giải phương trình ma trận tam giác trên là :
86
Chương trình 4-2
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define max 10
void main()
{
float a[max][max];
float b[max],x[max];
int i,j,k,n,t;
float s,c;
char tl;
clrscr();
printf("Cho so phuong trinh 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++)
{
printf("a[%d][%d] = ",i,j);
scanf("%f",&a[i][j]);
}
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++)
printf("%15.5f",a[i][j]);
printf("\n");
}
printf("\n");
87
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");
printf("\n");
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
printf("%15.5f",a[i][j]);
printf("\n");
}
printf("\n");
printf("Cho cac phan tu cua ma tran b : \n");
for (i=1;i<=n;i++)
{
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
printf("\n");
printf("Ma tran b ma ban da nhap");
printf("\n");
for (i=1;i<=n;i++)
printf("b[%d] = %10.5f\n",i,b[i]);
88
printf("\n");
flushall();
t=1;
while (t)
{
printf("Co sua ma tran b khong(c/k)?");
scanf("%c",&tl);
if (toupper(tl)=='C')
{
printf("Cho chi so hang can sua : ");
scanf("%d",&i);
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
if (toupper(tl)=='K')
t=0;
}
printf("\n");
printf("Ma tran b ban dau\n");
printf("\n");
for (i=1;i<=n;i++)
printf("b[%d] = %10.5f\n",i,b[i]);
printf("\n");
{
if (a[n][n]==0)
if (b[n]!=0)
printf("He da cho vo nghiem");
else
{
printf("He da cho co vo so nghiem");
x[n]=c;
}
else
x[n]=b[n]/a[n][n];
for (i=n-1;i>=1;i--)
{
s=0;
for (k=i+1;k<=n;k++)
89
s=s+a[i][k]*x[k];
x[i]=(b[i]-s)/a[i][i];
}
printf("\n");
printf("Nghiem cua he da cho la\n");
printf("\n");
for (i=1;i<=n;i++)
printf("x[%d] = %10.5f\n",i,x[i]);
getch();
}
}
Tuy nhiên, các hệ phương trình đơn giản hiếm khi gặp trong thực tế.
Các hệ phương trình tuyến tính có thể biểu diễn dưới dạng tam giác nếu định
thức của nó khác không, nghĩa là phương trình có nghiệm. Chúng ta biết rằng
các nghiệm của hệ không đổi nếu ta thay một hàng bằng tổ hợp tuyến tính
của các hàng khác. Như vậy bằng một loạt các biến đổi ta có thể đưahệ ban
đầu về dạng tam giác. Đó chính là nội dung của phương pháp loại trừ Gauss.
Chúng ta hãy xét hệ phương trình :
a x a x a x b
11
1
12
2
13
3
1
a x a x a x b
21
1
22
2
23
3
2
a31x1 a32x2 a33 x3 b3
Nhân hàng thứ nhất với a21/a11 ta có :
a21
a11
a21
a11
a21
a11
a21x1
a12x2
a13x3
b1
Số hạng đầu của phương trình bằng số hạng đầu của hàng thứ hai trong hệ
phương trình ban đầu. Khi trừ hàng một đã được biến đổi cho hàng 2 ta nhận
được hàng 2 mới
a21
a11
a21
a11
a21
a11
0x1 a22
a12 x2 a23
a13 x3 b2
b1
Ta tiếp tục cách này để loại trừ x1 ra khỏi hàng thứ 3. Phương trình trở thành
b
a
a12
a
a
x
1
11
1
13
2
0 a22
0 a32 a33
x b
23
2
x3
b3
với a,11 = a11 ; a,12 = a12 ; a,13 = a13 ; a,13 = a13 ; b,1 = b1
a21
a11
a21
a11
a31
a11
a22 a22
a12
a23 a23
a13
a32 a32
a12
90
a31
a11
a21
a11
a31
a11
a33 a33
a13
b2 b2
b1
b3 b3
b1
Ta loại trừ số hạng chứa x3 trong dòng thứ 3 bằng cách tương tự.Ta
nhân hàng thứ 2 trong hệ A'X = B' với a,32/a,22 và đem trừ đi hàng thứ 3 trong
hệ mới. Như vậy số hạng chứa x3 biến mất và ta nhận được ma trận tam giác
trên.
a12
b
a
a
a
x
1
11
1
13
0 a22
0
2
b3
x b
23
2
0
a33
x3
với a11 a11
a12 a12
a13 a13
b1 b1
a22 a22
a23 a23
a33
a32
b2 b2
a33 a33
a23
b3 b3
b2
a22
a22
Các phép tính này chỉ thực hiện được khi a11 0 và a,11 0.
Với một hệ có n phương trình, thuật tính hoàn toàn tương tự. Sau đây là
chương trình giải hệ phương trình n ẩn số bằng phương pháp loại trừ Gauss.
Chương trình 4-3
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define max 10
void main()
{
float b[max],x[max];
float a[max][max];
int i,j,k,n,t;
float c,s,d;
char tl;
clrscr();
printf("Cho so phuong trinh n = ");
scanf("%d",&n);
printf("Cho cac phan tu cua ma tran a :\n");
91
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");
printf("Ma tran a ma 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");
}
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++)
{
92
for (j=1;j<=n;j++)
printf("%15.5f",a[i][j]);
printf("\n");
}
printf("\n");
printf("Cho cac phan tu cua ma tran b : \n");
for (i=1;i<=n;i++)
{
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
printf("\n");
printf("Ma tran b ma ban da nhap\n");
printf("\n");
for (i=1;i<=n;i++)
printf("b[%d] = %15.5f\n",i,b[i]);
printf("\n");
flushall();
t=1;
while (t)
{
printf("Co sua ma tran b khong(c/k)?");
scanf("%c",&tl);
if (toupper(tl)=='C')
{
printf("Cho chi so hang can sua : ");
scanf("%f",&i);
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
if (toupper(tl)=='K')
t=0;
}
printf("\n");
printf("Ma tran b\n");
for (i=1;i<=n;i++)
printf("b[%d] = %15.5f\n",i,b[i]);
printf("\n");
93
for (k=1;k<=n-1;k++)
{
for (i=k+1;i<=n;i++)
{
b[i]=b[i]-b[k]*a[i][k]/a[k][k];
for (j=k+1;j<=n;j++)
a[i][j]=a[i][j]-a[k][j]*a[i][k]/a[k][k];
}
}
{
if (a[n][n]==0)
if (b[n]==0)
printf("He da cho vo nghiem");
else
{
printf("He da cho co vo so nghiem");
x[n]=c;
}
else
x[n]=b[n]/a[n][n];
for (i=n-1;i>=1;i--)
{
s=0;
for (k=i+1;k<=n;k++)
s=s+a[i][k]*x[k];
x[i]=(b[i]-s)/a[i][i];
}
printf("\n");
printf("Nghiem cua he da cho la\n");
printf("\n");
for (i=1;i<=n;i++)
printf("x[%d] = %15.5f\n",i,x[i]);
getch();
}
}
§2. PHƯƠNG PHÁP GAUSS - JORDAN
94
Xét hệ phương trình AX=B. Khi giải hệ bằng phương pháp Gauss ta đưa
nó về dạng ma trận tam giác sau một loạt biến đổi. Phương pháp khử Gauss-
Jordan cải tiến khử Gauss bằng cách đưa hệ về dạng :
EX = B*
và khi đó nghiệm của hệ chính là B*. Trong phương pháp Gauss-Jordan mỗi
bước tính phải tính nhiều hơn phương pháp Gauss nhưng lại không phải tính
nghiệm. Để đưa ma trận A về dạng ma trận E tại bước thứ i ta phải có aii = 1
và aij = 0. Như vậy tại lần khử thứ i ta biến đổi :
1.aij = aij/aii (j = i + 1, i + 2,..., n)
2.k = 1, 2,..., n
akj = akj - aijaki (j = i + 1, i + 2,..., n)
bk = bk - biaki
Ví dụ : Cho hệ
8 4
4 10
2 5 6.5 4
2
5
0
4
x
24
1
x2 32
x3 26
9 x4 21
0 4
4
Biến đổi lần 1: ta chia hàng 1 cho a11 = 8; nhân hàng 1 vừa nhận được với 4 và
lấy hàng 2 trừ đi; nhân hàng 1 vừa nhận được với 2 và lấy hàng 3 trừ đi; giữ
nguyên hàng 4 vì phần tử đầu tiên đã bằng 0 ta có
1 0.5 0.25 0
x
3
1
0
0
0
8
4
4
4
6
4
4
4
9
x2 20
x3 20
x4 21
Biến đổi lần 2 : ta chia hàng 2 cho a22 = 8; nhân hàng 2 vừa nhận được với 0.5
và lấy hàng 1 trừ đi; nhân hàng 2 vừa nhận được với 4 và lấy hàng 3 trừ đi;
nhân hàng 2 vừa nhận được với 4 và lấy hàng 4 trừ đi ta có :
1 0
0 1 0.5
0 0
0 0
0
0.25
0.5
2
x
1.75
2.5
10
1
x2
4
2
x3
7
x4
11
Biến đổi lần 3: Ta chia hàng 3 cho a33 = 4; giữ nguyên hàng 1; nhân hàng 3
vừa nhận được với 0.5 và lấy hàng 2 trừ đi; nhân hàng 3 vừa nhận được với 2
và lấy hàng 4 trừ đi ta có :
95
1 0 0 0.25
0 1 0 0.25
x
1.75
1.25
2.5
6
1
x2
0 0 1
0 0 0
0.5
6
x3
x4
Biến đổi lần 4: Ta chia hàng 4 cho a44 = 6; nhân hàng 4 vừa nhận được với -
0.25 và lấy hàng 1 trừ đi; nhân hàng 4 vừa nhận được với 0.25 và lấy hàng 2
trừ đi; nhân hàng 4 vừa nhận được với 0.5 và lấy hàng 3 trừ đi ta có :
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
x
2
1
x2 1
x3
2
x4 1
và ta có ngay vec tơ nghiệm.
Chương trình 4-4
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define spt 10
void main()
{
float a[spt][2*spt];
float b[spt];
int i,j,k,n,m,t;
float max,c;
char tl;
clrscr();
printf("Cho so phuong trinh 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++)
96
{
}
printf("a[%d][%d] = ",i,j);
scanf("%f",&a[i][j]);
printf("\n");
printf("Ma tran a ma ban da nhap");
printf("\n");
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
printf("%15.5f",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\n");
printf("\n");
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
printf("%15.5f",a[i][j]);
97
printf("\n");
}
printf("\n");
printf("Cho cac phan tu cua ma tran b : \n");
for (i=1;i<=n;i++)
{
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
printf("\n");
printf("Ma tran b ma ban da nhap\n");
printf("\n");
for (i=1;i<=n;i++)
printf("b[%d] = %15.5f\n",i,b[i]);
printf("\n");
t=1;
flushall();
while (t)
{
printf("Co sua ma tran b khong(c/k)?");
scanf("%c",&tl);
if (toupper(tl)=='C')
{
printf("Cho chi so hang can sua : ");
scanf("%d",&i);
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
if (toupper(tl)=='K')
t=0;
}
printf("\n");
printf("Ma tran b\n");
printf("\n");
for (i=1;i<=n;i++)
printf("%15.5f\n",b[i]);
printf("\n");
t=1;
98
flushall();
i=1;
while (t)
{
if (a[i][i]==0)
{
max=0;
m=i;
for (k=i+1;k<=n;k++)
if (max<fabs(a[k][i]))
{
m=k;
max=fabs(a[i][i]);
}
if (m!=i)
{
for (j=i;j<=n;j++)
{
c=a[i][j];
a[i][j]=a[m][j];
a[m][j]=c;
}
c=b[i];
b[i]=b[m];
b[m]=c;
}
if (m==i)
{
t=0;
printf("MA TRAN SUY BIEN");
}
}
if (a[i][i]!=0)
{
c=1/a[i][i];
for (j=i;j<=n;j++)
a[i][j]=a[i][j]*c;
b[i]=b[i]*c;
99
for (k=1;k<=n;k++)
if (k!=i)
{
c=a[k][i];
for (j=i;j<=n;j++)
a[k][j]=a[k][j]-a[i][j]*c;
b[k]=b[k]-b[i]*c;
}
}
i=i+1;
if (i==(n+1))
t=0;
}
if (i==(n+1))
{
printf("NGHIEM CUA HE");
printf("\n");
for (i=1;i<=n;i++)
printf("x[%d] = %15.5f\n",i,b[i]);
}
getch();
}
§3. PHƯƠNG PHÁP CHOLESKY
Trong phương pháp Cholesky một ma trận đối xứng A được phân tích
thành dạng A = RTR trong đó R là một ma trận tam giác trên.Hệ phương trình
lúc đó chuyển thành AX = RTRX = B. Như vậy trước hết ta phân tích ma trận A
thành tích hai ma trận. Sau đó giải hệ phương trình RTY = B và cuối cùng là hệ
RX = Y. Chương trình mô tả thuật toán này được cho dưới đây:
Chương trình 4-5
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define max 6
100
void main()
{
float a[max][max],r[max][max];
float b[max],x[max],y[max];
int i,j,k,l,n,t;
float s;
char tl;
clrscr();
printf("Cho so phuong trinh 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++)
{
printf("a[%d][%d] = ",i,j);
scanf("%f",&a[i][j]);
}
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++)
printf("%15.5f",a[i][j]);
printf("\n");
}
printf("\n");
flushall();
t=1;
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 : ");
101
scanf("%d",&i);
printf("Cho chi so cot can sua : ");
scanf("%d",&j);
printf("a[",i,",",j,"] = ");
scanf("%f",&a[i][j]);
}
if (toupper(tl)=='K')
t=0;
}
printf("Ma tran a\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");
printf("Cho cac phan tu cua ma tran b : \n");
for (i=1;i<=n;i++)
{
printf("b[%d] = ",i);
scanf("%f",&b[i]);
}
printf("\n");
printf("Ma tran b ma ban da nhap\n");
printf("\n");
for (i=1;i<=n;i++)
printf("b[%d] = %15.5f\n",i,b[i]);
printf("\n");
flushall();
t=1;
while (t)
{
printf("Co sua ma tran b khong(c/k)?");
scanf("%c",&tl);
if (toupper(tl)=='C')
{
102
Tải về để xem bản đầy đủ
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phương pháp tính - Chương 4: Giải hệ phương trình đại số tuyến tính", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_phuong_phap_tinh_chuong_4_giai_he_phuong_trinh_dai.doc