Bilangan kondisi bijak-norma vs bilangan kondisi bijak-komponen
Saya sedang membaca catatan kuliah saya untuk kelas aljabar linier numerik dan ada beberapa hal di bab ini yang mencakup bilangan kondisi yang tidak begitu saya mengerti.
Dua jenis nomor kondisi diperkenalkan, yang pertama diberikan oleh
$\kappa_{1}({f(\boldsymbol{x})} ; \boldsymbol{x})=\frac{\|\boldsymbol{J}(\boldsymbol{x})\|}{\|\boldsymbol{f}(\boldsymbol{x})\| /\|\boldsymbol{x}\|}$
dan yang kedua adalah
$\kappa_{2}(f(\boldsymbol{x}) ; \boldsymbol{x}) =\frac{\left|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right||\boldsymbol{x}|}{|f(\boldsymbol{x})|}$ .
Pertanyaan pertama saya adalah, apa perbedaan antara keduanya? Dikatakan bahwa kita dapat menggunakan nomor kondisi kedua ketika yang pertama memberikan hasil "pesimis", tetapi ini tampaknya sangat sewenang-wenang bagi saya.
Kemudian diturunkan bahwa bilangan kondisi kedua dapat dibatasi oleh yang pertama jika norma tak terhingga digunakan dan keluarannya $f$dianggap skalar. Untuk penurunan mereka menggunakan persamaan berikut
$\kappa_{1, \infty}(f ; \boldsymbol{x})=\frac{\left\|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right\|_{\infty}\|\boldsymbol{x}\|_{\infty}}{|f(\boldsymbol{x})|}$.
Karena transpos dari matriks Jacobian digunakan dan $J^T$ adalah vektor baris yang dapat ditulis sebagai $\left\|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right\|_{\infty}=\|\boldsymbol{J}(\boldsymbol{x})\|_{1}=\sum_{i=1}^{m}\left|[\boldsymbol{J}(\boldsymbol{x})]_{i}\right|$. Saya tidak mengerti mengapa kami menggunakan transpos dari$J$. Apakah mungkin untuk melakukan hal yang sama dengan$x$ atau apakah kita harus mengambil norma tak terbatas di sana?
Jawaban
Definisi Anda tentang dua kondisi angka tampaknya tidak konsisten satu sama lain. Hal yang sedikit mencuat adalah bahwa penulis yang berbeda mendefinisikan Jacobian secara berbeda. Beberapa menggunakan (A)$J_{ij} = \partial f_i / \partial x_j$ dan lainnya menggunakan (B) $J_{ij} = \partial f_j / \partial x_i$. Dengan definisi pertama, kami memiliki itu$f(x+\Delta x) = f(x) + J(x) \Delta x + O(\|\Delta x\|^2)$ dan dengan yang kedua kita dapatkan $f(x+\Delta x) = f(x) + J^\top(x) \Delta x + O(\|\Delta x\|^2)$. Definisi pertama tampaknya menggunakan definisi (A) dari Jacobian dan definisi kedua pasti membutuhkan definisi (B) untuk produk$|J^\top(x)||x|$untuk didefinisikan dengan baik. Dalam hal itu norma$\|\cdot\|$ adalah transpose-invariant $\|A\| = \|A^\top\|$tidak masalah definisi apa yang Anda gunakan. Ada cukup konsistensi notasi antara penulis yang berbeda sehingga sulit bagi saya untuk membedakan apa yang terjadi di sini. Saya memeriksa buku-buku aljabar linear numerik yang populer (Golub dan Van Loan, Trefethen dan Bau, Demmel, Higham) dan tidak dapat menemukan buku lain secara eksplisit menggunakan kumpulan definisi khusus ini. Mungkin jika Anda dapat menemukan sumber lain dengan kumpulan definisi ini, saya (atau orang lain) dapat membantu lebih jauh.
Izinkan saya sekarang menjawab pertanyaan utama Anda. Misalkan saya ingin menyelesaikan sistem diagonal persamaan linier
\ begin {persamaan} \ underbrace {\ begin {bmatrix} a & 0 \\ 0 & b \ end {bmatrix}} _ {= A} \ begin {bmatrix} x \\ y \ end {bmatrix} = \ begin { bmatrix} 1 \\ 1 \ end {bmatrix}. \ end {persamaan}
Ini sesuai dengan fungsinya $f(a,b) = (a^{-1},b^{-1})$ dengan Jacobian
$$ J(a,b) = -\begin{bmatrix} a^{-2} & 0 \\ 0 & b^{-2} \end{bmatrix} $$
yang memiliki norma $\|J(a,b)\| = \max(a^{-2},b^{-2})$ di operator $\infty$-norma. Mari kita asumsikan ke depan itu$a > b > 0$ begitu $\|J(a,b)\| = b^{-2}$. Maka, nomor kondisi pertama adalah
$$ \kappa_1(f(a,b);(a,b)) = \frac{\|J(a,b)\|}{\|f(a,b)\|/\|(a,b)\|} = \frac{b^{-2}}{b^{-1}/ a} = \frac{a}{b}. $$
Jadi jika $a\gg b$, masalah ini sangat buruk. Sekarang, mari kita lihat nomor kondisi dari segi komponen
$$ \kappa_2(f(a,b);(a,b)) = \frac{\begin{bmatrix} a^{-2} & 0 \\ 0 & b^{-2} \end{bmatrix}\begin{bmatrix}a\\ b\end{bmatrix}}{\begin{bmatrix} a^{-1} \\ b^{-1}\end{bmatrix}} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}. $$
Saya belum melihat definisi yang Anda berikan menggunakan pembagian vektor berdasarkan elemen, dan saya yakin jumlah kondisi komponen-bijaksana kanonik akan menjadi norma dari "bilangan kondisi vektor" ini. (mis. Menggunakan$\infty$-norma, $\kappa_2(f(a,b);(a,b)) = 1$.) Dengan menggunakan nomor kondisi dari segi komponen, masalahnya tampaknya terkondisi dengan baik! Apa yang terjadi disini?
Angka kondisi standar vanilla norm-bijaksana mengukur kira-kira seberapa banyak kita mengharapkan kesalahan relatif antara $f(x+\Delta x)$ dan $f(x)$ untuk dibandingkan dengan kesalahan relatif antara $x$ dan $x+\Delta x$. Secara khusus,
$$ \mbox{relative error in $f$} \le \kappa \cdot (\mbox{relative error in $x$}) + \mbox{higher order terms}. $$
Jika kita berkata $(a+\Delta a, b+\Delta b)$ memiliki kesalahan relatif, katakanlah, $10^{-6}$ dalam $\infty$-norm dibandingkan dengan nilai sebenarnya $(a,b)$ ini berarti kesalahan $\Delta a$ dan $\Delta b$ di setiap komponen lebih kecil dari $10^{-6}\|(a,b)\| = 10^{-6}a$. Perhatikan bahwa jika$a$ lebih dari $10^6b$, maka ini berarti kesalahan $\Delta b$ bisa lebih besar dari $b$diri! Tapi saat kita benar-benar mengevaluasi$f$, $a^{-1}$ jauh lebih kecil dari $b^{-1}$ tapi $b$ telah terganggu oleh kesalahan besar $\Delta b$ dan dengan demikian kesalahan relatif dalam $f$ (sebagian besar didominasi oleh kesalahan relatif dari $b^{-1}$sangat tinggi. Akibatnya, jika seseorang mempertimbangkan kesalahan relatif berdasarkan norma, kesalahan relatif dari komponen kecil vektor dapat dibuat sangat besar dan kesalahan besar dari segi komponen ini dapat diperkuat jika$f$ tergantung pada entri kecil dari inputnya.
Dalam banyak pengaturan praktis, kami memiliki vektor input yang setiap komponen memiliki kesalahan relatif kecil. Misalnya jika error$\Delta a$ dan $\Delta b$ adalah hasil dari pendekatan bilangan real sembarang $a$ dan $b$ dengan angka floating point, kita punya itu $|\Delta a| \le \epsilon |a|$ dan $|\Delta b| \le \epsilon |b|$ untuk konstanta kecil $\epsilon$. Jadi, skenario terburuk dalam kasus terakhir ini tidak mungkin, tetapi tidak ada cara untuk membuktikan bahwa menggunakan norma sebagai, jika kita hanya berasumsi,$\|(\Delta a, \Delta b)\| \le \epsilon \|(a,b)\|$, tidak ada cara untuk menunjukkannya $\Delta b$ relatif kecil terhadap $b$. Angka kondisi dari segi komponen melakukan hal ini dengan tepat. Mereka memungkinkan Anda untuk mengukur pengkondisian masalah relatif terhadap gangguan kecil dari segi komponen dalam input, yang memungkinkan kontrol yang jauh lebih baik atas kesalahan relatif dalam nilai kecil dalam vektor input.
Pada akhirnya, saya masih harus mengatakan baris "kita dapat menggunakan nomor kondisi kedua ketika yang pertama memberikan hasil 'pesimis'" karena tidak ada heuristik yang mencakup semua untuk secara definitif menunjukkan kapan pengkondisian komponen akan atau menang tidak memberikan batasan kesalahan yang jauh lebih baik. Namun, saya berharap contoh yang saya berikan adalah ilustrasi yang mengungkapkan bagaimana pengkondisian berdasarkan norma dapat memberikan batasan kesalahan pesimis yang menyesatkan untuk suatu masalah dan bagaimana pengkondisian yang bijaksana komponen dapat memberikan batasan yang lebih realistis.
Ekspresi untuk $\kappa_2$ tidak masuk akal kecuali $f(x)$adalah skalar. Ekspresi yang diberikan untuk$\kappa_1$ dan $\kappa_2$ bukanlah definisi, tetapi teorema.
Dalam jawaban ini saya akan secara ketat mendefinisikan bilangan kondisi relatif normwise dan bilangan kondisi relatif komponen. Ini harus menjelaskan perbedaan mereka.
Membiarkan $\Omega \subseteq \mathbb{R}^n$ jadilah satu set terbuka, biarkan $f : \Omega \rightarrow \mathbb{R}^m$ dan biarkan $x \in \Omega$. Jika$x \not = 0$ dan jika $f(x) \not = 0$, lalu angka kondisi relatif normwise $\kappa_f^{nr}$didefinisikan sebagai berikut. Pertama kita mendefinisikan fungsi bantu \ begin {persamaan} \ kappa_f ^ {nr} (x, \ delta) = \ sup \ left \ {\ frac {\ | f (x) -f (y) \ |} {\ | f (x) \ |} \ besar / \ frac {\ | xy \ |} {\ | x \ |} \:: \: 0 <\ | xy \ | <\ delta \ | x \ | \Baik \}. \ end {persamaan} di mana$\delta > 0$ adalah sejumlah seperti itu $$ \{ y \in \mathbb{R}^n \: : \: \|x\| < \delta \|x\|) \subseteq \Omega. $$ Jelas bahwa fungsinya $\delta \rightarrow \kappa_f^{nr}(x,\delta)$tidak negatif dan tidak merosot. Karena itu batasnya$$ \underset{\delta \rightarrow 0_.}{\lim} \kappa_f^{nr}(x,\delta) $$ada. Ini memungkinkan kita untuk menentukan jumlah kondisi relatif normwise$\kappa_f^{nr}$ sebagai berikut $$ \kappa_f^{nr}(x) = \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{nr}(x,\delta).$$
Angka kondisi relatif normwise memberikan batasan yang tegas pada kesalahan relatif normwise yang dapat dicapai. Jika$y \in \Omega$ memuaskan $\|x-y\| \leq \delta \|x\|$, kemudian $$ \frac{\|f(x)-f(y)\|}{\|f(x)\|} = \left(\frac{\|f(x)-f(y)\|}{\|f(x)\|} \big/ \frac{\|x-y\|}{\|x\|}\right) \frac{\|x-y\|}{\|x\|} \leq \kappa_f^{nr}(x,\delta) \frac{\|x-y\|}{\|x\|} $$ Apalagi jika $\delta$ cukup kecil, lalu $$ \kappa_f^{nr}(x,\delta) \approx \kappa_f^{nr}(x) $$adalah perkiraan yang bagus. Oleh karena itu, kita tidak dapat mengharapkan kesalahan relatif normwise yang lebih kecil dari$$ \frac{\|f(x)-f(y)\|}{\|f(x)\|} \approx \kappa_f^{nr}(x,\delta) \frac{\|x-y\|}{\|x\|}. $$Dari definisi ini dimungkinkan untuk membuktikan hasil berikut. Jika$f : \Omega \rightarrow \mathbb{R}^m$adalah juga terdiferensiasi pada titik$x \in \Omega$, kemudian $$ \kappa_f^{nr}(x) = \frac{\|Df(x)\|\|x\|}{\|f(x)\|} $$ dimana $Df(x) \in \mathbb{R}^{m \times n}$ adalah Jacobian dari $f$ pada intinya $x$. Untuk lebih jelasnya, jika$A = Df(x)$ adalah Jacobian dari $f$ di $x$, kemudian $a_{ij} = \frac{\partial f_i}{\partial x_j}(x)$.
Sekarang untuk mendefinisikan nomor kondisi relatif componentwise, pertama-tama kita mendefinisikan kesalahan relatif componentwise. Membiarkan$x \in \mathbb{R}^n$ menunjukkan nilai target dan biarkan $y \in \mathbb{R}^n$menunjukkan perkiraan tersebut. Kemudian kesalahan relatif secara komponen diberikan oleh \ begin {persamaan} \ rho (x, y) = \ max \ left \ {\ frac {| x_j - y_j |} {| x_j |} \:: \: j = 1, 2, \ dotsc, n \ right \}, \ end {persamaan} di mana kami memperluas definisi pecahan biasa untuk menyertakan \ begin {persamaan} \ frac {a} {b} = \ begin {kasus} 0 & a = 0 \ wedge b = 0, \\ \ infty & a> 0 \ wedge b = 0. \ end {cases} \ end {persamaan} Sekarang mari$x \in \Omega$ menjadi titik seperti itu $x_j \not = 0$ untuk semua $j$ dan $f_i(x) \not = 0$ untuk semua $i$. Kita mulai dengan mendefinisikan fungsi bantu$\kappa_f^{cr}$ diberikan oleh $$ \kappa_f^{cr}(x,\delta) = \sup \left\{ \frac{\rho(f(x),f(y))}{\rho(x,y)} \: : \: 0 < \rho(x,y) < \delta \right\}. $$ Jelas itu $\delta \rightarrow \kappa_f^{cr}(x,\delta)$adalah fungsi nonnegatif dan nondecreasing. Karena itu batasnya$$ \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{cr}(x,\delta) $$ada dan tidak negatif. Hal ini memungkinkan kita untuk menentukan jumlah kondisi relatif dari segi komponen$f$ sebagai berikut $$ \kappa_f^{cr}(x) = \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{cr}(x,\delta). $$Jumlah kondisi relatif berdasarkan komponen memberlakukan batas yang tegas pada akurasi komponen yang dapat dicapai. Jika$y \in \Omega$ seperti itu $0 < \rho(x,y) < \delta$, kemudian $$ \rho(f(x),f(y)) = \left(\frac{\rho(f(x),f(y))}{\rho(x,y)}\right) \rho(x,y)\leq \kappa_f^{cr}(x,\delta) \rho(x,y). $$ Apalagi jika $\delta$ cukup kecil, lalu $$ \kappa_f^{cr}(x,\delta) \approx \kappa_f{cr}(x) $$adalah perkiraan yang bagus. Oleh karena itu, kita tidak dapat mengharapkan kesalahan relatif komponen yang lebih kecil dari$$ \rho(f(x),f(y)) \approx \kappa_f^{cr}(x,\delta) \rho(x,y). $$Dari definisi tersebut dimungkinkan untuk membuktikan hasil sebagai berikut. Jika$f$adalah juga terdiferensiasi di$x \in \Omega$, kemudian $$ \kappa_f^{cr}(x) = \left \|\frac{|Df(x)||x|}{|f(x)|} \right\|_\infty. $$Di sini sangat penting untuk menghargai fakta bahwa pembagian di sisi kanan adalah komponen kapan$f$ adalah fungsi vektor.
Jelas bahwa kedua nomor kondisi tersebut mengukur kepekaan $f$untuk kecil perubahan input, tetapi mereka bergantung pada definisi yang berbeda dari "kecil". Jika$f$ juga merupakan fungsi skalar, yaitu jika $m = 1$, maka kita punya $$ \kappa_f^{cr}(x) = \left \|\frac{|Df(x)||x|}{|f(x)|} \right\|_\infty = \frac{\||Df(x)||x|\|_\infty}{|f(x)|} \leq \frac{\||Df(x)|\|_\infty\||x|\|_\infty}{\|f(x)\|_\infty} = \frac{\|Df(x)\|_\infty\|x\|_\infty}{\|f(x)\|_\infty} =\kappa_f^{nr}(x). $$Dalam hal ini, kita melihat bahwa bilangan kondisi relatif normwise selalu lebih besar dari bilangan kondisi komponen. Namun, saya merasa agak menyesatkan untuk menyatakan bahwa angka kondisi relatif normatif lebih pesimis daripada angka kondisi komponen, hanya karena mereka menggunakan definisi "kecil" yang berbeda.
Banyak kebingungan dapat dihindari dengan selalu menyatakan secara jelas domain dan codomain dari fungsi yang dimaksud. Faktanya, sebuah fungsi sebenarnya adalah rangkap tiga $(f,U,V)$ terdiri dari sebuah domain $U$, domain bersama $V$ dan aturan $f$ untuk menetapkan ke elemen yang tepat di domain $U$ tepat satu elemen di domain bersama $V$. Sayangnya, notasi yang mapan cenderung hanya berfokus pada aturan $f$.
Definisi dari bilangan kondisi relatif secara komponen yang digunakan di sini diekstrak dari makalah "Bilangan kondisi campuran, berdasarkan komponen dan terstruktur" oleh Gohberg dan Koltracht, SIAM J. Matrix Anal. Appl., 14 (3), halaman 688–704, 1993.