上節(jié)課主要介紹了非線性方程的幾種數(shù)值解法解恰,其中包括交叉法(二分法、線性插值法)和開放法(牛頓法浙于、割線法护盈、固定點法)。本節(jié)課主要介紹線性方程組的數(shù)值求解方法羞酗,主要分為直接法和迭代法兩類腐宋。直接法包括高斯消去法(Gauss elimination)、高斯約當法(Gauss-Jordan)以及LU分解法,迭代法包括Jacobi法和高斯塞德爾法(Gauss-Seidel) 胸竞。
1. 高斯消去法(Gauss Elimination Method)
高斯消去法是通過將線性方程組轉(zhuǎn)化為上三角的形式欺嗤,然后一步一步回代(back substitution)求解的方法。
例:
- 系統(tǒng)法:
- 系統(tǒng)法的增廣矩陣形式:將方程寫為矩陣的形式
系統(tǒng)法的求解過程可以寫成如下增廣矩陣的變換形式
例:
matrix:
類似的卫枝, 形式的方程組:
可以寫作如下矩陣形式:
高斯消去法的核心:
- 方程組寫為矩陣形式
- 矩陣行變換:將一行中所有元素乘上一個標量煎饼,減去(加上)另外一行,該操作不會改變方程的解
- 逐行變換校赤,直至將矩陣轉(zhuǎn)換為便于求解的形式
一般而言吆玖,如下三種矩陣形式方便求解:
- 對角形式:
,
- 上三角形式:
痒谴,使用回代法求解(back substitution):
重復下去
- 下三角形式 :
使用前向替換法(forward substitution):
重復下去
Matlab實現(xiàn)(求解, 使用左除
):
>> A = [1 2;3 4]
A =
1 2
3 4
>> b = [5 6]'
b =
5
6
>> x = A\b
x =
-4.0000
4.5000
>> format long
>> x = A\b
x =
-3.999999999999999
4.499999999999999
MATLAB實現(xiàn)(高斯消去法):
function x=Gauss(a,b)
ab=[a,b];
[R,C]=size(ab);
for j=1:R-1
for i=j+1:R
ab(i,j:C)=ab(i,j:C)-ab(i,j)/ab(j,j)*ab(j,j:C);
end
end
x=zeros(R,1);
x(R)=ab(R,C)/ab(R,R);
for i=R-1:-1:1
x(i)=(ab(i,C)-ab(i,i+1:R)*x(i+1:R))/ab(i,i);
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>> A = [1 2;3 4]
A =
1 2
3 4
>> b = [5 6]'
b =
5
6
>> format long
>> Gauss(A,b)
ans =
-4.000000000000000
4.500000000000000
MATLAB實現(xiàn)(回代法與前向替換法)
function y = BackwardSub(a,b)
% The function solves a system of linear equations ax=b
% where a is upper triangular by using backward substitution.
% Input variables:
% a The matrix of coefficients.
% b A column vector of constants.
% Output variable:
% y A colum vector with the solution.
n = length(b);
y(n,1) = b(n)/a(n,n);
for i = n-1:-1:1
y(i,1)=(b(i)-a(i,i+1:n)*y(i+1:n,1))./a(i,i);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function y = ForwardSub(a,b)
% The function solves a system of linear equations ax=b
% where a is lower triangular by using forward substitution.
% Input variables:
% a The matrix of coefficients.
% b A column vector of constants.
% Output variable:
% y A colum vector with the solution.
n = length(b);
y(1,1) = b(1)/a(1,1);
for i = 2:n
y(i,1)=(b(i)-a(i,1:i-1)*y(1:i-1,1))./a(i,i);
end
2. 高斯主元消去(Gauss Pivoting)
可以發(fā)現(xiàn)衰伯,當主元為或非常小時铡羡,使用高斯消去法會失去精度积蔚,因此,在必要時可以交換行的順序:
高斯主元法就是通過交換行的順序烦周,來保證主元不為0尽爆,并且盡可能取絕對值較大的值,下面通過一個案例读慎,說明主元很小時漱贱,高斯消去法會造成計算精度上出現(xiàn)較大誤差,而高斯主元法的計算結(jié)果會更為精確夭委。
例: 使用高斯消去:
-
(round-off error, since
)
MATLAB運算結(jié)果:
>> A = [0.0003 12.34;0.4321 1]
A =
0.000300000000000 12.340000000000000
0.432100000000000 1.000000000000000
>> b = [12.343 5.321]'
b =
12.343000000000000
5.321000000000000
>> A\b
ans =
10.000000000000000
1.000000000000000
若交換行序(高斯主元消去):
-
(round-off error, since
)
MATLAB實現(xiàn)(高斯主元消去)
function x=GaussPivot(a,b)
ab=[a,b];
[R,C]=size(ab);
for j=1:R-1
if ab(j,j)==0
for k=j+1:R
if ab(k,j)~=0
abTemp=ab(j,:);
ab(j,:)=ab(k,:);
ab(k,:)=abTemp;
break
end
end
end
for i=j+1:R
ab(i,j:C)=ab(i,j:C)-ab(i,j)/ab(j,j)*ab(j,j:C);
end
end
x=zeros(R,1);
x(R)=ab(R,C)/ab(R,R);
for i=R-1:-1:1
x(i)=(ab(i,C)-ab(i,i+1:R)*x(i+1:R))/ab(i,i);
end
end
3. 高斯約當法(Gauss-Jordan Method幅狮, 同時適用于求矩陣的逆)
高斯約當法一般采用高斯主元消去法,不同的是株灸,高斯約當法每次會將主元規(guī)范化為崇摄,且最終將原矩陣轉(zhuǎn)化為單位矩陣。
例:
可以看到慌烧,高斯約當法可以很方便地用來求解一個矩陣的逆:,
4. LU分解法(LU-decomposition Method)
LU分解是將一個矩陣分解為一個下三角矩陣和上三角矩陣的乘積:, 其中
表示下三角矩陣,
表示上三角矩陣逐抑。LU分解之后,求解線性方程
就等價于求解如下兩個方程:
LU分解主要有兩種方法來實現(xiàn):
- 高斯消去(Gauss Elimination);
- Crout's Method
4.1 Crout's Method
例:
采用待定系數(shù)法求解:
結(jié)合計算過程屹蚊,可以推導出厕氨,對于矩陣,使用Crout's Method進行LU分解的通用形式為:
-
矩陣的第一列
-
矩陣的對角元素
-
矩陣的第
行
-
矩陣的其他元素
-
矩陣的其他元素
MATLAB實現(xiàn)(LU分解汹粤,Crout's Method)
function [L, U] = LUdecompCrout(A)
% The function decomposes the matrix A into a lower triangular matrix L
% and an upper triangular matrix U, using Crout's method such that A=LU.
% Input variables:
% A The matrix of coefficients.
% Output variable:
% L Lower triangular matrix.
% U Upper triangular matrix.
[R, C] = size(A);
for i = 1:R
L(i,1) = A(i,1);
U(i,i) = 1;
end
for j = 2:R
U(1,j)= A(1,j)/L(1,1);
end
for i = 2:R
for j = 2:i
L(i,j)=A(i,j)-L(i,1:j-1)*U(1:j-1,j);
end
for j = i+1:R
U(i,j)=(A(i,j)-L(i,1:i-1)*U(1:i-1,j))/L(i,i);
end
end
4.2 高斯消去
general formulation:
例:
高斯消去法進行LU分解也可以通過待定系數(shù)法求解出矩陣參數(shù):
-
矩陣第一行:
-
矩陣對角元素:
-
矩陣第一列:
-
矩陣其他元素:
-
矩陣其他元素:
MATLAB實現(xiàn)(LU分解,高斯法嘱兼,待定系數(shù))
function [L,U] = LUdecopGauss(A)
[R,C] = size(A);
for i = 1:C
L(i,i) = 1;
U(1,i) = A(1,i);
end
for i = 2:R
L(i,1) = A(i,1)/U(1,1);
end
for j = 2:C
for i = 2:j
U(i,j) = A(i,j)-L(i,1:i-1)*U(1:i-1,j);
end
for i= (j+1):R
L(i,j) = (A(i,j)-L(i,1:j-1)*U(1:j-1,j))/U(j,j);
end
end
end
高斯消去的待定系數(shù)法與Crout's 方法的待定系數(shù)法相比冯丙,要難以理解,可讀性差,主要在于通解形式與常規(guī)的求解順序不一致胃惜。為便于理解泞莉,還有一種拉格朗日形式來實現(xiàn)高斯消去法:
回顧高斯消去的過程:
- 第一步運算
這是一步行變換
- 第二步運算
- 第
步運算后
此時即為LU分解中的U矩陣,而
可以看到
MATLAB實現(xiàn)(LU分解船殉,高斯消去鲫趁,拉格朗日形式)
function [L,U]=LUGauss2(A)
[R,C]=size(A);
L = zeros(size(A));
for i = 1:C
L(i,i) = 1;
end
for j=1:R-1
for i=j+1:R
L(i,j) = A(i,j)/A(j,j);
A(i,j:C)=A(i,j:C)-A(i,j)/A(j,j)*A(j,j:C);
end
end
U = A;
end
5. 總結(jié)
本節(jié)課主要介紹了求解線性方程組的幾種直接法,包括高斯消去利虫、高斯主元消去挨厚、高斯約當、LU分解法等糠惫,其中高斯約當法可以用來求矩陣的逆疫剃。 矩陣的LU分解又可以通過高斯消去和Crout 方法來實現(xiàn),對參數(shù)矩陣進行LU分解后硼讽,很容易可以求解方程巢价。下節(jié)課介紹求解線性方程組的迭代法。