Download NUMET_zbirka PDF

TitleNUMET_zbirka
File Size2.3 MB
Total Pages438
Document Text Contents
Page 1

Desanka P. Radunović

Aleksandar B. Samardžić

Filip M. Marić

N U M E R I Č K E

M E T O D E

Zbirka zadataka

kroz C, Fortran i Matlab

AKADEMSKA MISAO
Beograd, 2005

Page 219

6.4. QR METODA 209

Kona•cno, trodijagonalna matrica sli•cna polaznoj je

A(0) = T2A1T2 =







2.2 −2.2913 0 0
−2.2913 3.5476 1.7325 0

0 1.7325 0.3000 1.0906
0 0 1.0906 −0.0476







Matricu A(0) razla•zemo na proizvod unitarne i gornje trougaone matrice A(0) =
Q(0)R(0) primenom Givens-ove metode rotacije.

Prvo se svodi na nulu element a21 matricom rotacije:

U12 =







0.6916 −0.7213 0 0
0.7213 0.6916 0 0

0 0 1 0
0 0 0 1







•sto daje matricu

U12A
(0) =







3.1765 −4.1459 −1.2497 0
0 0.8043 1.1999 0
0 1.7325 0.3000 1.0906
0 0 1.0906 −0.0476







Zatim se svodi na nulu element a32 matricom rotacije

U23 =







1 0 0 0
0 0.4211 0.9070 0
0 −0.9070 0.4211 0
0 0 0 1







•sto daje matricu

U23 U12A
(0) =







3.1765 −4.1459 −1.2497 0
0 1.9100 0.7773 0.9893
0 0 −0.9621 0.4592
0 0 1.0907 −0.0475







Kona•cno, na nulu se svodi element a43 matricom rotacije

U34 =







1 0 0 0
0 1 0 0
0 0 0.6615 −0.7499
0 0 0.7499 0.6615







tako da se dobija gornje trougaona matrica

R(0) = U34 U23 U12A
(0) =







3.1765 −4.1459 −1.2497 0
0 1.9101 0.7773 0.9893
0 0 −1.4544 0.3394
0 0 0 0.3130







Page 220

210 6. SOPSTVENE VREDNOSTI I SOPSTVENI VEKTORI MATRICA

Unitarna matrica Q(0) je

Q(0) = U>12U
>
23U

>
34 =







0.6926 0.3037 −0.4328 −0.4907
−0.7213 0.2916 −0.4156 −0.4711

0 0.9070 0.2786 0.3158
0 0 −0.7499 0.6615







Posle prvog koraka QR algoritma dobija se trodijagonalna matrica

A(1) = R(0)Q(0) =







5.1906 −1.3778 0 0
−1.3778 1.2620 −1.3191 0

0 −1.3191 −0.6597 −0.2347
0 0 −0.2347 0.2070







Ponavljaju¶ci ovaj postupak dobijamo da su sopstvene vrednosti date matrice

λ1 = 5.6520, λ2 = 1.5454, λ3 = −1.4201, λ4 = 0.2226.

C Pri implementaciji QR metode, prvo se poziva procedura householder()
koja vr•si svo -denje polazne matrice. Zatim se u petlji vr•si QR dekompozicija i
izra•cunava nova vrednost date matrice; ovaj postupak se ponavlja sve dok se ne
postigne •zeljena ta•cnost. Kriterijum za prekid iterativnog postupka je isti kao kod
Jacobi-jeve metode.

QR dekompozicija se vr•si matricama rotacije. Parametar ϕ se odre -duje tako
da matrica rotacije Gk,l(ϕ) anulira element na poziciji (l, k) matrice A. Ukoliko je
B ≡ Gk,l(ϕ) ·A va•zi da je

bk,i = ak,i cos(ϕ)− al,i sin(ϕ)
bl,i = ak,i sin(ϕ) + al,i cos(ϕ), i = 1, n

bi,j = ai,j , j 6= k, l

Iz uslova da je bl,k nula, sledi da je

bl,k = ak,k sin(ϕ) + al,k cos(ϕ) = 0

Mo•ze se pretpostaviti da je al,k 6= 0 jer je u suprotnom Gk,l(ϕ) = I. Ukoliko
podelimo prethodnu jedna•cinu sa



a2k,k + a
2
l,k sledi da je

sin(ϕ) = − al,k√
a2k,k + a

2
l,k

, cos(ϕ) =
ak,k



a2k,k + a
2
l,k

Procedura qr() na taj na•cin ima oblik:

#include <assert.h>

#include <math.h>

#include <stdlib.h>

#include <string.h>

Page 437

Literatura

[1] Aljan•ci¶c S., Uvod u realnu i funkcionalnu analizu, Gra -devinska knjiga,
Beograd, 1968.

[2] Bahvalov N.S., Numerical Methods, Mir Publishers, Moscow, 1977.

[3] Berezin I.S., •Zidkov N., Numerička analiza, Nau•cna knjiga, Beograd, 1963.

[4] Davis P., Interpolation and Approximation, Dover Publications, New York,
1975.

[5] Demidovich B.P., Maron I.A., Computational Mathematics, Mir Publishers,
Moscow, 1987.

[6] Fox L., Parker J.B., Chebyshev Polynomials in Numerical Analysis, Oxford
University Press, London, 1972.

[7] Gustafsson F.,Bergman N., MATLAB for Engineers Explained, Springer,
London, 2003.

[8] Hageman L.,Young D., Applied Iterative Methods, Academic Press, New
York, 1981.

[9] Hall G., Watt J.M. (editors), Modern Numerical Methods for Ordinary
Differential Equations, Clarendon Press, Oxford, 1976.

[10] Higham D.J.,Higham N.J., MATLAB Guide, SIAM, Philadelphia, 2000.

[11] Hildebrand F.B., Introduction to Numerical Analysis, McGraw{Hill, New
York, 1974.

[12] Hildebrand F.B., Advanced Calculus for Applications, Prentice{Hall, En-
glewood Clifis, N.J., 1976.

[13] Jovanovi¶c B., Radunovi¶c D., Numerička analiza, Nau•cna knjiga, 1993.

[14] Kernigan B., Ri•ci D., Programski jezik C, Savremena administracija, 1992.

[15] Moler C.B., Numerical Computing with MATLAB, SIAM, Philadelphia,
2004.

427

Page 438

428 LITERATURA

[16] Oden J.T., Reddy J.N., An Introduction to the Mathematical Theory of
Finite Elements, Wiley, New York, 1976.

[17] Ortega J., Numerical Analysis – A Second Course, SIAM, Philadelphia,
1990.

[18] Ortega J., Rheinboldt W., Iterative Solutions of Nonlinear Equations in
Several Variables, Academic Press, New York, 1970.

[19] Parlett B., The Symmetric Eigenvalue Problem, Prentice{Hall, Englewood
Clifis, N.J., 1980.

[20] Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P., Numerical
Recipes in C, Cambridge University Press, 1992

[21] Radunovi¶c D., Numeričke metode, Univerzitet u Beogradu, 1998.

[22] Ralston A., A First Course in Numerical Analysis, McGraw{Hill, Tokyo,
1965.

[23] Samard•zi¶c A., GNU programerski alati, Matemati•cki fakultet Univerziteta
u Beogradu, 2001.

[24] Stoer J., Bulirsch R., Introduction to Numerical Analysis, Springer{Verlag,
New York 1980.

[25] Strang G., Introduction to Applied Mathematics, Willesley{Cambridge
Press, 1986.

[26] http://www.gnu.org/software/libmatheval/

[27] http://www.matf.bg.ac.yu/r3nm/

Similer Documents