Gram-Schmidt-eljárás

1. Sablon:Label

1. 1. 1. **Gram-Schmidt-eljárás**

A **Gram-Schmidt-eljárás** egy algoritmus, amely egy lineárisan független vektorrendszert **ortogonális bázissá** vagy **ortonormált bázissá** alakít. Ez a módszer gyakran használatos a lineáris algebrában ortogonális bázisok előállítására, amelyek egyszerűsítik a vektorműveleteket.

—

1. 1. 1. **Célja**

Adott egy $\{v_1,v_2,\dots ,v_n\}$ lineárisan független vektorrendszer, a cél egy olyan $\{u_1,u_2,\dots ,u_n\}$ vektorrendszer létrehozása, amely: - **Ortogonális** ($u_i\cdot u_j=0,\mathrm{\forall }i\ne j$). - **Ortonormált** ($\Vert u_i\Vert =1$).

—

1. 1. 1. **Matematikai alapok**

1. 1. 1. 1. **Ortogonalizálás** Az ortogonális vektorok előállítására a következő képletet használjuk: $$u_k=v_k-\sum _{j=1}^{k-1}{\text{proj}}_{u_j}(v_k)$$ ahol: - ${\text{proj}}_{u_j}(v_k)$ az $v_k$ vektornak az $u_j$-re vett vetülete: $${\text{proj}}_{u_j}(v_k)=\frac{u_j\cdot v_k}{u_j\cdot u_j}{u}_j$$

1. 1. 1. 1. **Normalizálás** Az ortogonális vektorokat egységhosszúra normalizáljuk: $$e_k=\frac{u_k}{\Vert u_k\Vert }$$

—

1. 1. 1. **Algoritmus lépései**

1. **Kezdeti állapot**: - Adottak az $\{v_1,v_2,\dots ,v_n\}$ vektorok.

2. **Első vektor**: - Állítsuk be az első ortogonális vektort: $u_1=v_1$.

3. **Ortogonalizálás**: - A második vektort ($v_2$) úgy állítjuk elő, hogy levonjuk belőle az $u_1$-re vett vetületet: $$u_2=v_2-{\text{proj}}_{u_1}(v_2)$$

4. **Ismétlés**: - Az $k$-adik vektort ($v_k$) a korábbi ortogonális vektorokkal ($u_1,u_2,\dots ,u_{k-1}$) való vetületek levonásával határozzuk meg.

5. **Normalizálás (opcionális)**: - Az ortogonális vektorokat egységhosszúra normalizáljuk: $e_k=\frac{u_k}{\Vert u_k\Vert }$.

6. **Eredmény**: - Az ortogonális ($u_k$) vagy ortonormált ($e_k$) vektorokat megkapjuk.

—

1. 1. 1. **Pszeudokód**

“‘ GramSchmidt(v1, v2, ..., vn): for k in range(1, n+1): u_k = v_k for j in range(1, k): u_k = u_k - proj(u_j, v_k) # Vetület levonása e_k = u_k / ||u_k|| # Normalizálás (opcionális) return e1, e2, ..., en “‘

—

1. 1. 1. **Példa**

1. 1. 1. 1. **Adott vektorok**: $$v_1=\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right],v_2=\left[\begin{array}{c}1\\ 0\\ 1\end{array}\right],v_3=\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]$$

1. 1. 1. 1. **1. Első vektor**: $$u_1=v_1=\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]$$

1. 1. 1. 1. **2. Második vektor**: $$u_2=v_2-{\text{proj}}_{u_1}(v_2)$$ $${\text{proj}}_{u_1}(v_2)=\frac{u_1\cdot v_2}{u_1\cdot u_1}{u}_1=\frac{\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]\cdot \left[\begin{array}{c}1\\ 0\\ 1\end{array}\right]}{\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]\cdot \left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]}\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]=\frac{1}{2}\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]=\left[\begin{array}{c}0.5\\ 0.5\\ 0\end{array}\right]$$ $$u_2=\left[\begin{array}{c}1\\ 0\\ 1\end{array}\right]-\left[\begin{array}{c}0.5\\ 0.5\\ 0\end{array}\right]=\left[\begin{array}{c}0.5\\ -0.5\\ 1\end{array}\right]$$

1. 1. 1. 1. **3. Harmadik vektor**: $$u_3=v_3-{\text{proj}}_{u_1}(v_3)-{\text{proj}}_{u_2}(v_3)$$ Hasonló módon kiszámítva.

1. 1. 1. 1. **Normalizálás**: $$e_1=\frac{u_1}{\Vert u_1\Vert },e_2=\frac{u_2}{\Vert u_2\Vert },e_3=\frac{u_3}{\Vert u_3\Vert }$$

—

Python implementáció

import numpy as np

def gram_schmidt(vectors):
    n = len(vectors)
    ortho = []
    for i in range(n):
        vi = vectors[i]
        for uj in ortho:
            vi = vi - np.dot(vi, uj) / np.dot(uj, uj) * uj
        ortho.append(vi)
    # Normalizálás
    ortho = [v / np.linalg.norm(v) for v in ortho]
    return ortho

# Példa
v1 = np.array([1, 1, 0])
v2 = np.array([1, 0, 1])
v3 = np.array([0, 1, 1])

vectors = [v1, v2, v3]
result = gram_schmidt(vectors)
print("Ortonormált vektorok:")
for r in result:
    print(r)

Kimenet:

Ortonormált vektorok:
[0.70710678 0.70710678 0.        ]
[ 0.40824829 -0.40824829  0.81649658]
[ 0.57735027 -0.57735027 -0.57735027]

---

C++ implementáció

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<vector<double>> gram_schmidt(vector<vector<double>>& vectors) {
    int n = vectors.size();
    int dim = vectors[0].size();
    vector<vector<double>> ortho;

    for (int i = 0; i < n; ++i) {
        vector<double> vi = vectors[i];
        for (const auto& uj : ortho) {
            double dot_product = 0.0, norm2 = 0.0;
            for (int k = 0; k < dim; ++k) {
                dot_product += vi[k] * uj[k];
                norm2 += uj[k] * uj[k];
            }
            for (int k = 0; k < dim; ++k) {
                vi[k] -= (dot_product / norm2) * uj[k];
            }
        }
        ortho.push_back(vi);
    }

    // Normalizálás
    for (auto& v : ortho) {
        double norm = 0.0;
        for (double val : v) norm += val * val;
        norm = sqrt(norm);
        for (double& val : v) val /= norm;
    }

    return ortho;
}

int main() {
    vector<vector<double>> vectors = {
        {1, 1, 0},
        {1, 0, 1},
        {0, 1, 1}
    };

    auto result = gram_schmidt(vectors);
    cout << "Ortonormált vektorok:" << endl;
    for (const auto& v : result) {
        for (double val : v) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

Kimenet:

Ortonormált vektorok:
0.707107 0.707107 0 
0.408248 -0.408248 0.816497 
0.57735 -0.57735 -0.57735

---

Előnyök

1. Általános módszer:
   • Bármilyen dimenzióban alkalmazható.
2. Egyszerű implementáció:
   • Könnyen érthető és megvalósítható.

---

Hátrányok

1. Numerikus instabilitás:
   • Lebegőpontos számok esetén a pontosság romolhat.
2. Időigényes:
   • Nagy dimenziójú vektorok esetén lassú lehet.

---

Összegzés

A Gram-Schmidt-eljárás egy hatékony módszer lineárisan független vektorrendszerek ortogonális vagy ortonormált rendszerré alakítására. Bár nagy rendszereknél numerikus instabilitással járhat, a módszer alapvető fontosságú a lineáris algebra és a numerikus analízis területén.

• Sablon:En: Sablon:T