eroarea absoluta = |x - xk| <= b-a / 2^k+1^> functia f definita pe [a,b], epsilon
loop log2( b-a /| supra epsilon) +1 times
x = a + (b - a)/2
if f(x) == 0
return last x
if f(a)f(x) < 0
b = x
else
a = x
- Are solutie unica daca:
f(a) f(b) < 0
La fiecare pas, x_aprox = intersectia cu axa OX a tangentei in punctul x, f(x) epsilon il luam 10^-3^
Teorema:
- C^2^([a,b]), f', f'' nu se anuleaza pe [a,b]
f(a) f(b) < 0.- x0 din [a,b],
f(x0) f''(x0) > 0
Atunci f(x) = 0 are solutie unica, iar sirul xk ramane in [a,b] si converge la solutie.
Oprire: cand either
- abs f(new_x) < epsilon (eroarea f)
- |new_x - x| / |x| < epsilon (eroarea x)
Algoritm:
f, f', x0 care satisface conditia din teorema, epsilon
loop
new_x = x - f(x)/f'(x)
if |new_x - x| / |x| < epsilon
break
x = new_x
f, a, b, x0, x1, epsilon
f(a) f(b) < 0f'(x) != 0
Atunci:
- f are solutie unica
Exista Δ: x0, x1 din [x - Δ,x + Δ] din [a,b]atunci lista solutiilor ramane in intervalul ala
Algoritm:
x, new_x se aleg corect!
loop
if |new_x - x| / |x| < epsilon
break
new_new_x = x f(new_x) - new_x f(x) | supra f(new_x) - f(x)
A patratica superior triunghiulara, b vector
calculezi x[n] logic
for k from n-1 to 1
x[k] = b[k] - fiecare col elem dupa el * solutia | supra A acolo
A, matrice cu determinantul diferit de 0
for each line
A * B(line) = I(line)
-> se obtine un sistem cu n necunoscute
-> Gauss
Matrice -> Matrice superior triunghiulara
A = A | b
for k = 1 to n-1
gasim pivot de sub (inclusiv)A(k,k):
1. fara pivotare = primul diferit de 0
2. piv. partiala = maximul
interschimbam linia lui cu linia k
for each elem under
its Line = Line - elem/pivot * (Line k)
A = A | b
for k = 1 to n-1
gasim pivot = maximul din orice linie/col sub linia k
interschimbam linia lui cu linia k
interschimbam coloana lui cu coloana k
for each elem under
its Line = Line - elem/pivot * (Line k)
A patratica superior triunghiulara, b vector
calculezi x[n] logic
for k from n-1 to 1
x[k] = b[k] - (inmultesti fiecare coloana dupa el cu solutia) | supra A acolo
A(m, n), toleranta
rang = 0
incepem cu iter = stanga sus
pivot = maximul coloanei sub (inclusiv) iter
if pivot < toleranta
move iter right
continue
inteschimba liniile pivot <-> iter
for each elem sub
Line elem -= elem/iter * Line iter
move iter right and down
rang++
Descompunerea unei matrice in produs de o matrice inferior triunghiulara si una superior triunghiulara: A = L * U
Deci, pentru un sistem A*x = b, avem L * U * x = b si:
- U*x = y, de aici aflam x trivial
- L*y = b, de aici aflam y trivial
L si U se afla:
U = A aflat prin orice metoda Gauss
1 0 0
L = m21 1 0
m31 m32 1
Cod:
L = I
w = 1..n
for k = 1 to n-1
pivot = maximul abs coloanei k sub (inclusiv)
if pivot = 0 error
A: interschimba line pivot <-> line k
w(p) <-> w(k)
if k > 1
L(pivot, 1:k-1) <-> L(k, 1:k-1)
for i = k+1 to n
L(i,k) = A(i,k)/A(k,k)
A(i) = A(i) - L(i,k) A(k)
if A(n,n) = 0 error
U = A
- prima linie cu prima coloana
- prima linie cu a doua coloana
- ...etc... = prima linie
<u, v> = u1*v1 + u2*v2 + ...
A matrice □ L matrice □5 Fie A o matrice □-ica Fie L o matrice □-ica, inferior triunghiulara (se deduce) Descompunerea Cholesky: A = LL^T^
Are descompunere Cholesky daca (oricare v din R^n^):
- A simetrica (A^T^ = A)^T^ = A <=> simetrica
- <Av, v> >= 0 | atunci, <=> semipozitiv definita
- <Av, v> > 0 | atunci <==> pozitiv definita
Descompunerea este unica daca:
- Elementele de pe diagonala principala din L sunt > 0
Algoritm:
> Matricea A pozitiv definita, vector b
Pentru k = 1 to n
L[k, k] = sqrt | A[k, k] - Sum (s = 1:k-1) de L[k, s]^2
Pentru i > k
L[i, k] = 1/L[k,k] (/) A[i, k] - Sum (s = 1:k-1) de L[i, s]*L[k, s]
Pseudocod
L(Col 1) = A(Col 1) / sqrt A(1,1)
pentru fiecare linie r:
alpha = sqrt | A(r,r) - (suma patratelor tuturor elementelor dinainte pe aceeasi linie)
L(r,r) = alpha
fiecare element din coloana de sub ea = A acolo - suma (L linia aia pana acolo).*(L linia de deasupra pana acolo)
|si totul supra alpha
restul 0 peste tot
x = SubsAsc(L, b)
y = SubsDesc(L^T, y)
A v = lambda v
sau
(A - lambda I) v = 0
P(lambda) = det(A - lambda I)
Radacinile lui P(lambda) sunt lambdzile
Spectrul lui A: multimea lambdzilor = Sigma(A) Raza spectrala: = Ro(A) = max abs(lambdas) Note: Daca o lambda e complexa, atunci abs(lambda) = sqrt | a^2^ + b^2^
R(x) = [ cosx sinx; -sinx cosx ]
A simetrica □, epsilon = 10^-4^
while |A| > epsilon
A(p,q) = max | modul | elem strict deasupra diag principale
if A(p,p) = A(q,q)
a = Pi/4
else
a = 1/2 arctg | 2A(p,q) / A(q,q)-A(p,p)
for j = 1 to n
if j != p sau q
u = cosa A(p,j) - sina A(q,j)
v = sina A(p,j) + cosa A(q,j)
A(p,j) = A(j,p) = u
A(q,j) = A(j,q) = v
u = cosa^2 A(p,p) - 2 cosa sina A(p,q) + sina^2 A(q,q)
v = sina^2 A(p,p) + 2 cosa sina A(p,q) + cosa^2 A(q,q)
A(p,p) = u
A(q,q) = v
A(p,q) = A(q,p) = 0
lambda = diagonala principala A
v = (v1...n )^T^
- Norma 1 = || v ||1 = suma | modulurile elementelor
- Norma 2 = || v ||2 = sqrt | suma | patratele elementelor
- Norma infinit = || v || infinit = max | modulurile elementelor
Norma matriciala:
- Subordonata normei vectoriale 1: || A || 1 = max | suma modulelor pe fiecare coloana
- Subordonata normei vectoriale infinit: || A || infinit = max | suma modulelor elem pe fiecare linie
Teorema 1: B = A^T^A, lambda 1..n = valorile proprii ale lui B || A ||2 = max | sqrt | fiecare lambda
Teorema 2: Oricare A, B: || AB || <= || A || || B ||
Numarul de conditionare pt A relativ la norma 1/2/infinit p: A matrice, det A != 0 Kp(A) = || A ||p || A^-1^ ||p Sau, pe scurt, K(A) = ||A|| ||A^-1^||
Teorema 3: K2(A) = sqrt lambdan / sqrt lambda1 (lambda pentru B)
Criteriul de convergenta a metodei Jacobi: A inversabila, deci metoda Jacobi este convergenta si Ro(I - A) < 1
= sir recurent x(k) unde x(k+1) = B x(k) + b x(0) arbitrar Metoda este convergenta == Ro(B) < 1 (Raza spectrala)
A inversabila, epsilon
q = || I - A ||
if q >= 1 error "Metoda Jacobi nu asigura convergenta"
x = 0
B = I - A
b = a
loop
new x = B x + b
if || new x - x || / x < epsilon break
Matrice diagonal dominata: modulul fiecarui element de pe diagonala >= suma modulelor celorlalte elemente de pe linie
A inversabila, epsilon
if A not diagonal dominata: error
x = 0
for i = 1 to n
for j = 1 to n
B(i,j) = delta(i,j) - A(i,j)/A(i,i)
for i = 1 to n
B(i) = A(i) / A(i,i)
loop
new x = B x + b
if || new x - x || / || x || < epsilon break
A simetrica si pozitiv definita
Algoritm: Pornim cu x[0] = 0 si vectorul a se da. Tau = 2 / (lambda[n] + lambda[1]) - lambda sunt valorile proprii ale matricei A care se da - Note: Poate Tau se da.
x[k] = (I - Tau * A) * x[k-1] + Tau * a
Pseudocod:
for i = 1 to n
for j = 1 to n
Sigma(O) <- B(i,j) = delta(i,j) - Sigma(O) A(i,j)
for i = 1 to n
B(i) = Sigma(O) A(i)
x = 0
loop
new x = B x + B(sigma) calculati mai devreme
if || new x - x || / || x || < epsilon break (pentru A)
x(1...n+1) = puncte/noduri de interpolare Gasim Polinomul Pn(x) = a(1) + a(2)x + ... + a(n+1)x^n^
Pn(x(i)) = f(x(i))
Ce inseamna: Daca avem un set de puncte (x, f(x)), dar nu stim functia f, ci doar punctele prin care trece, putem sa estimam cam cum e functia. Functia gasita este polinomul de interpolare
P2(x) = a1 + a2 x + a3 x^2
Metoda directa:
-
Aflam a1, a2, a3 pentru care:
a1 + a2x1 + a3x1^2 = y1 a1 + a2x2 + a3x2^2 = y2 a1 + a2x3 + a3x3^2 = y3 -
Daca x si y sunt necunoscute, folosim formula:
ai = |Ai| / |A|
Metoda Lagrange:
- Vezi pagina 2 Exemplul #2
Metoda Newton:
-
f[x1...xn] = f[x2...xn+1] - f[x1...xn] (/) xn+1 - x1
f[x1] = f(x1) f[x1,x2] = f(x2) - f(x1) (/) x2 - x1 f[x1,x2,x3] = f[x2,x3] - f[x1,x2] (/) x3 - x1 -
Vezi tabelul de la pagina 4, stanga sus
-
Daca se dau date de interpolare (x, y) atunci il iei pe DD0 ca y (adica f(x) = y)
Pentru o funtie f(x) cu diviziunea (x1, x2, x3): S(x) = f(x) in punctele date, ca inainte, la polinomul de interpolare
S(x) =
if x in [x1, x2): S1(x)
if x in [x2, x3]: S2(x)
S1(x) = a1 + b1(x - x1)
S2(x) = a2 + b2(x - x2)
Dar:
S1(x2) = S2(x2)
Da, la sfarsit vom avea o functie pe cazuri
Se dau puncte de forma (x, f(x))
S(x) =
if x in [x1, x2): a1 + b1(x-x1) + c1(x-x1)^2 + d1(x-x1)^3 = S1(x)
if x in [x2, x3): a1 + b1(x-x2) + c1(x-x2)^2 + d1(x-x1)^3 = S2(x)
Avem, deci, 8 necunoscute. Avem urmatoarele ecuatii:
S1(x2) = S2(x2)
S1'(x2) = S2'(x2)
S1''(x2) = S2''(x2)
S(x1) = f(x1)
S(x2) = f(x2)
S(x2) = f(x2)
De obicei, in cerinta se dau inca doua ecuatii. Rezulta 8 ecuatii, 8 necunoscute => putem afla necunoscutele.
Se da o integrala de la a la b
FT(f) = (b - a) / 2 | * (f(a) + f(b))
FTS(f) = (b-a)/2m * | f(x(1)) + f(x(m+1)) + Sum i = 2 to m | f(x(j))
FS(f) = Intg a to b | f(x) dx
= Sum k = 1 to m | Intg x(2k-1) to x(2k+1) | f(x) dx