11차시 - 반복법과 역행렬 (1)

1. 반복법

1) 야코비 반복법이란?

임의로 추측한 방정식의 해가 오차 범위에 도달할 때까지 되풀이 하는 방법
계수 행렬이 0을 많이 포함하는 연립방정식의 해를 구할 경우에 가우스(Gauss)의 소거법 보다 빠르게 수행할 수 있음.

 

- 방정식의 a11, a22, a33원소의 절대값이 가장 큰 원소로 만듦.

 

- 해를 구하기 위해서 보기 1의 방정식(1)를 x1에 대해서 (2)를 x2에 대해서, (3)를 x3에 대해서 보기 2와 같이 품.

 

x1, x2, x3의 값을 임으로 추측하고, 추측한 값을 x1^(0),x2^(0),x3^(0)이라함.

x1^(0), x2^(0), x3^(0) 값을 보기 1에 대입하여 x1^(1), x2^(1), x3^(1) 를 구함.

 

 

2) 오차한계 지정

• 오차
  - 계산기로 연속적인 양을 표현할 때, 이산적인 수치를 이용하여 나타냄.
  - 예를 들면 x2=2의 방정식의 올바른 해는 √2=1.414로 무한한 수이지만, 계산기의 내부에서는 유한한 수의 이산적인 수치로 나타냄.
  - 실제값(true value)과 다른 근사치(approximation)로 표현
• 절대오차 한계
  - 절대오차한계를 ε이라고 할 때 모든 i=1, 2, ..., n에 대해서 다음을 만족하면 해를 택함.
  

• 상대오차 한계
  - 상대오차한계를 τ라고 할 때 모든 i=1, 2, ...n에 대해서 다음을 만족하면 해를 택함.

 

 

3) 야코비 반복법의 알고리즘

Set iteration = 1
While(k < = max_iteration) 
{
	for i = a to N new
	if | new X – old X | < TOL 
	Set iteration = iteration+1 
	For i=1 to N old
} 
stop

 

 

4) MATLAB을 이용한 야코비 반복법

A=[7,5,3;2,5,4;2,2,6]; 
B=[2;2;2]; 
X0=[0;0;0];

Tol=0.1; %허용오차 
Max=100 %허용오차

[n,m]=size(A)

X_old=x0; 
C=-A;

For(i=1:n) 
	C(i,i)=0;
	C(i,:)=C(i,:)/A(i,i);
	D(i,1)=B(i)/A(i,i); 
end

Disp(‘반복횟수 x1, x2, x3, x4....’); 
For(i=1:max)
	X_new=C*X_old+D; 
	if(norm(X_new-X_old) <= tol)
		disp(‘Jacobi법이 수렴하였습니다.’);
		break; 
	else
	end 
	disp([i,X_new’]);
	count=i;
end

if(cound >= max)
	disp(‘Jacobi법이 수렴하였습니다.’); 
	x=X_new
end 
X

 

 

5) 가우스-사이델 반복법이란?

• 카코비법을 개량한 방법
• 연립방정식에 대응하는 행렬을 두 개의 삼각행렬로 분해한 뒤 해를 반복적으로 계산해 수렴시키는 방식을 사용

 

 

6) 가우스-사이델 반복법의 알고리즘

 

 

7) MATLAB을 이용한 가우스-사이델 반복법

function [x,G,c] = gsmp(A,b,n,z) 
%
% x = gsmp(A,b,n,z)
%
% Gauss-Seidel iteration on system A*x = b with printing
% using matrix multiplication (not optimal)
% n -- number of iterations
% z -- initial vector (default 0) 
%
% x -- final iterate
% G -- Gauss-Seidel matrix
% c -- Gauss-Seidel vector 
%

if nargin <=3, z=0*b; end
LD = tril(A);
G = -LD\triu(A,1); 
c = LD\b;
x=z;
For i = 1:n
	x = G*x + c;
	fprintf(1, ’%3d ’,i) 
	fprintf(1,’%5.5f ‘,x’)
	fprintf(1,’\n’)
end

 

 

8) SOR 방법이란?

• SOR 방법은 Successive Over Relaxation method의 약어, 연속적 완화가속법이라고도 함.
• Gauss-Seidel법을 확장한 방법
• 상수 ω(완화변수, Relaxation Parameter)를 이용
• SOR방법의 k번째 근사값은 SOR방법으로 구한 k-1번째 근사값과 Gauss-Seidel 방법으로 구한 k번째 근사값을 이용하여 Gauss-Seidel방법보다 더 빨리 수렴할 수 있음.
• Gauss-Seidel 방법으로 구한 근사값을 xj 라 하면 SOR방법으로 구한 k번째 근사해는 다음과 같이 정의함.

• 보기 1의 양변에 대각행렬 D를 곱함.

• 보기 2와 같이 되어 i=1, 2, ...n에 대하여 보기 3과 같음.

• ω는 보기 4와 같음.

• P는 행렬 D^(-1)*(L+U)의 고유치 중 절대값이 가장 큰 수

 

 

9) SOR 방법의 알고리즘

 

 

10) MATLAB을 이용한 SOR 법

A=[7,5,3;2,5,4;2,2,6]; 
B=[2;2;2]; 
x0=[0;0;0];
W=1.1;
tol=0.1;
max=100;
[n,m]=size(A); %행렬의 크기 구함 
X_new=x0;
C=-A;

for(i=1:n) %C,D 행렬로 변환 
	C(i,i)=0;
	C(i,:)=C(i,:)/A(i,i);
	D(i,1)=b(i)/A(i,i);
end

disp(‘반복횟수 x1 x2 x3 x4 .......’); 
for(i=1:max) %SOR 알고리즘
	for(j=1:n) 
		X_new(j)=(1-W)*X_old(j)+W*(C(j,:)*X_new+D(j)); 
	end

	if(norm(X_old-X_new)<=tol) %수렴조건 
		disp(‘SOR법이 수렴하였습니다.’); 
		break;
	end 
	disp([i,X_new’]); 
	count=i;
end

if(cound >= max) %해가 수렴하지 않았을 경우 
disp(‘해가 수렴하지 않았습니다.’);
end

x