Norma Matriks dan Bilangan Kondisi

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

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

Norma vektor yang dipilih menentukan norma matriks terinduksinya.

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\\|x\\|_2=\sqrt{x^{\mathsf T}x}$

Untuk matriks persegi, radius spektral adalah

Setiap norma matriks terinduksi membatasi radius spektral:

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

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

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

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

Untuk matriks simetris yang dapat diinverskan, rumus ini menjadi

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.

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

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

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.

Bandingkan sistem awal $Ax=b$ dengan sistem yang matriks dan vektornya berubah sedikit.

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

Jika syarat tersebut terpenuhi, perubahan relatif solusi dibatasi oleh

\frac{\|\delta x\|}{\|x\|}\le\frac{\kappa(A)}{1-\kappa(A)\|\delta A\|/\|A\|}\left(\frac{\|\delta b\|}{\|b\|}+\frac{\|\delta A\|}{\|A\|}\right)

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 menjelaskan dua sifat yang berbeda:

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)$ .

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\\|x\\|_2=\sqrt{x^{\mathsf T}x}$

Norma Matriks dan Bilangan Kondisi

Norma matriks terinduksi

Norma Matriks dan Bilangan Kondisi

Norma matriks terinduksi

Radius spektral dan norma spektral

Bilangan kondisi penyelesaian linear

Sensitivitas Sistem Diagonal Dua Dimensi

Batas Perubahan Solusi

Kondisi Masalah dan Stabilitas Algoritma