Norma Matriks dan Bilangan Kondisi

Norma matriks terinduksi

Norma vektor mengukur ukuran vektor. Norma matriks yang terinduksi mengukur faktor terbesar peregangan vektor oleh sebuah matriks:

\|A\|=\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}=\max_{\|x\|=1}\|Ax\|

Definisi ini langsung memberikan dua batas penting bagi matriks dan vektor yang dimensinya sesuai:

\|Ax\|\le\|A\|\|x\|

$Norma vektor yang dipilih$ menentukan norma matriks terinduksi.

Norma vektor	Norma matriks terinduksi
$\displaystyle\\|x\\|_1=\sum_{i=1}^{n}\lvert x_i\rvert$	$\displaystyle\\|A\\|_1=\max_j\sum_i\lvert a_{ij}\rvert$ , jumlah absolut kolom terbesar
$\displaystyle\\|x\\|_\infty=\max_i\lvert x_i\rvert$	$\displaystyle\\|A\\|_\infty=\max_i\sum_j\lvert a_{ij}\rvert$ , jumlah absolut baris terbesar
$\displaystyle\\|x\\|_2=\sqrt{x^{\mathsf T}x}$	$\displaystyle\\|A\\|_2=\sigma_{\max}(A)$ , nilai singular terbesar

Radius spektral dan norma spektral

Untuk matriks persegi, radius spektral adalah

\rho(A)=\max_{\lambda\in\operatorname{spec}(A)}|\lambda|

Setiap norma matriks terinduksi membatasi radius spektral:

\rho(A)\le\|A\|

Norma spektral memenuhi

\|A\|_2=\sigma_{\max}(A)=\sqrt{\lambda_{\max}(A^{\mathsf T}A)}

Jika $A$ adalah matriks simetris real, nilai singularnya adalah nilai absolut dari nilai eigennya, sehingga

\|A\|_2=\max_i|\lambda_i(A)|=\rho(A)

Untuk matriks nonnormal umum, radius spektral dan norma spektral $tidak harus sama$ .

Bilangan kondisi penyelesaian linear

Untuk matriks persegi yang dapat diinverskan dan sebuah norma terinduksi, definisikan

\kappa(A)=\|A\|\|A^{-1}\|

Bilangan kondisi setidaknya satu. Matriks singular memiliki bilangan kondisi tak hingga. Dalam norma Euklides,

\kappa_2(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}

Untuk matriks simetris yang dapat diinverskan, rumus ini menjadi

\kappa_2(A)=\frac{\max_i|\lambda_i(A)|}{\min_i|\lambda_i(A)|}

Gunakan nilai eigen dengan $magnitudo terkecil$ pada penyebut. Tanda positif atau negatif tidak menentukan pilihan ini.

Ukuran $\kappa(A)$	Artinya
Dekat $1$	Pada kasus terburuk, perubahan relatif pada data $b$ menghasilkan perubahan relatif pada solusi yang hampir sama besar.
Besar	Perubahan data $b$ pada arah tertentu dapat menghasilkan perubahan relatif yang jauh lebih besar pada solusi.
Tak hingga	Matriks singular, sehingga masalah invers tidak memiliki solusi unik.

Sensitivitas Sistem Diagonal Dua Dimensi

Perhatikan

A=\begin{pmatrix}1&0\\0&\varepsilon\end{pmatrix},\qquad 0<\varepsilon\ll1

Nilai singularnya adalah $1$ dan $\varepsilon$ , sehingga

\kappa_2(A)=\frac{1}{\varepsilon}

Untuk $b=(b_1,b_2)^{\mathsf T}$ , solusinya adalah

x=A^{-1}b=\begin{pmatrix}b_1\\b_2/\varepsilon\end{pmatrix}

Perubahan kecil pada $b_2$ $diperbesar sebesar$ $1/\varepsilon$ pada komponen solusi kedua. Matriks tersebut mendekati singular karena vektor pada arah koordinat kedua dikalikan dengan $\varepsilon$ yang mendekati nol.

Ambil $\varepsilon=1/1000$ dan bandingkan dua ruas kanan. Hanya pengamatan kedua yang berubah.

$b$	$x=A^{-1}b$
$(1,1/1000)^T$	$(1,1)^T$
$(1,2/1000)^T$	$(1,2)^T$

\Delta b_2=\frac1{1000},\qquad\Delta x_2=\frac{1/1000}{1/1000}=1

Batas Perubahan Solusi

Asumsikan $A$ dapat diinverskan dan $b\ne0$ , agar galat relatif berikut memiliki $penyebut tak nol$ . Bandingkan sistem awal $Ax=b$ dengan sistem yang matriks dan vektornya berubah sedikit.

(A+\delta A)(x+\delta x)=b+\delta b

Gunakan norma terinduksi yang sama untuk semua besaran. Batas berikut memerlukan syarat

\kappa(A)\frac{\|\delta A\|}{\|A\|}<1

Jika syarat tersebut terpenuhi, perubahan relatif solusi dibatasi oleh

\begin{aligned} \frac{\|\delta x\|}{\|x\|} &\le\frac{\kappa(A)}{1-\kappa(A)\|\delta A\|/\|A\|} \\ &\quad{}\cdot\left(\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right) \end{aligned}

Batas ini menunjukkan perubahan solusi $terbesar yang mungkin terjadi$ . Pada banyak perubahan kecil, perubahan solusi lebih kecil daripada batas tersebut.

Kondisi Masalah dan Stabilitas Algoritma

$kondisi masalah$ menjelaskan $sensitivitas masalah matematis terhadap perubahan masukan$
$stabilitas$ menjelaskan besar galat tambahan yang diperkenalkan oleh algoritma numerik

Algoritma stabil tidak dapat menghilangkan sensitivitas yang memang terdapat pada masalah berkondisi buruk. Sebaliknya, masalah berkondisi baik masih dapat diselesaikan dengan buruk oleh implementasi yang tidak stabil. Residual kecil $\|b-A\hat{x}\|$ saja juga tidak menjamin galat maju kecil $\|x-\hat{x}\|$ ketika $\kappa(A)$ besar.

Dalam komputasi numerik, estimasikan kebalikan bilangan kondisi dari faktorisasi yang tepercaya. Jangan membentuk $A^{-1}$ secara eksplisit hanya untuk mengevaluasi $\kappa(A)$ .