Algoritma Lanczos - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T03:06:20Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 03.06
Baris 1:		Baris 1:
	'''Algoritma Lanczos''' adalah [[algoritme\|algoritma]] iteratif adaptasi dari metode daya (''power method'') untuk menemukan <math>m</math> nilai dan vektor eigen yang "paling berguna" (umumnya yang tertinggi/terendah) dari sebuah [[matriks Hermite]] berukuran <math>n \times n</math>, dengan <math>m</math> tidak perlu jauh lebih kecil dari <math>n</math>. Algoritma ini dirancang oleh [[Cornelius Lanczos]] pada tahun 1950. Meskipun secara prinsip metode ini efisien dalam aspek [[komputasi]], metode yang dirancang pada awalnya tidak berguna karena sifatnya yang tidak stabil secara numerik.		'''Algoritma Lanczos''' adalah [[algoritme\|algoritma]] iteratif adaptasi dari metode daya (''power method'') untuk menemukan <math>m</math> nilai dan vektor eigen yang "paling berguna" (umumnya yang tertinggi/terendah) dari sebuah [[matriks Hermite]] berukuran <math>n \times n</math>, dengan <math>m</math> tidak perlu jauh lebih kecil dari <math>n</math>. Algoritma ini dirancang oleh [[Cornelius Lanczos]] pada tahun 1950.<ref>C. Lanczos. [https://www.cs.umd.edu/~oleary/lanczos1950.pdf An iteration method for the solution of the eigenvalue problem of linear differential and integral operators]. ''J. Res. Nat’l Bur. Std''. 1950. Vol. 45. hlm. 255–282.</ref> Meskipun secara prinsip metode ini efisien dalam aspek [[komputasi]], metode yang dirancang pada awalnya tidak berguna karena sifatnya yang tidak stabil secara numerik.

	Pada tahun 1970, Ojalvo dan Newman menunjukkan cara membuat metode ini stabil secara numerik, dan mengaplikasikannya untuk menemukan mode getaran dari sebuah struktur teknik berukuran besar. Hal ini dicapai dengan menggunakan sebuah teknik untuk 'memurnikan' vektor-vektor Lanczos (misal dengan mengortogonalkan secara berulang setiap vektor yang baru ditemukan dengan ''semua'' vektor yang sudah ditemukan) sampai ke suatu akurasi yang diinginkan. Jika teknik tidak diterapkan, metode akan menghasilkan vektor-vektor yang sangat 'terkontaminasi' oleh vektor-vektor yang berasosiasi dengan [[frekuensi]] alami yang rendah.		Pada tahun 1970, Ojalvo dan Newman menunjukkan cara membuat metode ini stabil secara numerik, dan mengaplikasikannya untuk menemukan mode getaran dari sebuah struktur teknik berukuran besar.<ref name=":0">I. U. Ojalvo. ''Vibration modes of large structures by an automatic matrix-reduction method''. ''AIAA Journal''. 1970. Vol. 8 (7). hlm. 1234–1239. doi:10.2514/3.5878.</ref> Hal ini dicapai dengan menggunakan sebuah teknik untuk 'memurnikan' vektor-vektor Lanczos (misal dengan mengortogonalkan secara berulang setiap vektor yang baru ditemukan dengan ''semua'' vektor yang sudah ditemukan)<ref name=":0" /> sampai ke suatu akurasi yang diinginkan. Jika teknik tidak diterapkan, metode akan menghasilkan vektor-vektor yang sangat 'terkontaminasi' oleh vektor-vektor yang berasosiasi dengan [[frekuensi]] alami yang rendah.

	Dalam karyanya, Ojalvo dan Newman juga mengusulkan cara memilih vektor awal (''starting vector;'' misalnya dengan menggunakan [[Pembangkitan bilangan acak\|pembangkit bilangan acak]]), dan mengusulkan metode menentukan nilai <math> m </math> secara empiris (sebaiknya dipilih kurang lebih 1.5 kali dari banyak nilai eigen akurat yang diinginkan). Kontribusi lain diberikan oleh Paige, yang juga memberikan analisis galat untuk metode ini. Pada tahun 1988, Ojalvo memberikan sejarah yang lebih akurat dari algoritma ini, dan sebuah uji galat nilai eigen yang efisien.		Dalam karyanya, Ojalvo dan Newman juga mengusulkan cara memilih vektor awal (''starting vector;'' misalnya dengan menggunakan [[Pembangkitan bilangan acak\|pembangkit bilangan acak]]), dan mengusulkan metode menentukan nilai <math> m </math> secara empiris (sebaiknya dipilih kurang lebih 1.5 kali dari banyak nilai eigen akurat yang diinginkan). Kontribusi lain diberikan oleh Paige, yang juga memberikan analisis galat untuk metode ini.<ref>C. C. Paige. ''The computation of eigenvalues and eigenvectors of very large sparse matrices''. U. of London. 1971.</ref><ref>C. C. Paige. ''Computational Variants of the Lanczos Method for the Eigenproblem''. ''J. Inst. Maths Applics''. 1972. Vol. 10 (3). hlm. 373–381. doi:10.1093/imamat/10.3.373.</ref> Pada tahun 1988, Ojalvo memberikan sejarah yang lebih akurat dari algoritma ini, dan sebuah uji galat nilai eigen yang efisien.<ref>I. U. Ojalvo. ''Proc. 6th Modal Analysis Conference (IMAC), Kissimmee, FL''. 1988. hlm. 489–494.</ref>

	== Algoritma ==		== Algoritma ==
	Algoritma ini memerlukan sebuah [[matriks Hermite]] <math> A </math> berukuran <math> n \times n </math>, dan secara opsional sebuah bilangan <math> m </math> yang menyatakan banyak iterasi yang diinginkan. Jika nilai <math> m </math> tidak ditentukan, umumnya diambil <math> m=n </math>. Sebenarnya, algoritma tidak memerlukan akses ke matriks secara eksplisit, melainkan sebuah fungsi <math>v \mapsto A v</math> yang menghasilkan produk [[perkalian matriks]] dengan vektor. Fungsi ini dipanggil paling banyak <math> m </math> kali. Pada proses iterasi, algoritma rentan terhadap ketidakstabilan numerik. Ketika dieksekusi dalam [[aritmetika]] non-eksak (''non-exact arithmetic''), pertimbangan-pertimbangan tambahan harus diambil untuk memastikan validitas hasil (dijelaskan di bagian selanjutnya). Di akhir iterasi, algoritma akan menghasilkan sebuah [[matriks ortonormal]] <math> V </math> berukuran <math> n \times m </math> dan sebuah [[Matriks simetrik\|matriks simetrik real]] tridiagonal <math>T = V^* A V</math> berukuran <math> m \times m </math>. Dalam kasus <math> m = n </math>, maka <math> V </math> akan berupa [[matriks uniter]], dan matriks <math> A = V T V^* </math>.		Algoritma ini memerlukan sebuah [[matriks Hermite]] <math> A </math> berukuran <math> n \times n </math>, dan secara opsional sebuah bilangan <math> m </math> yang menyatakan banyak iterasi yang diinginkan. Jika nilai <math> m </math> tidak ditentukan, umumnya diambil <math> m=n </math>. Sebenarnya, algoritma tidak memerlukan akses ke matriks secara eksplisit, melainkan sebuah fungsi <math>v \mapsto A v</math> yang menghasilkan produk [[perkalian matriks]] dengan vektor. Fungsi ini dipanggil paling banyak <math> m </math> kali. Pada proses iterasi, algoritma rentan terhadap ketidakstabilan numerik. Ketika dieksekusi dalam [[aritmetika]] non-eksak (''non-exact arithmetic''), pertimbangan-pertimbangan tambahan harus diambil untuk memastikan validitas hasil (dijelaskan di bagian selanjutnya). Di akhir iterasi, algoritma akan menghasilkan sebuah [[matriks ortonormal]] <math> V </math> berukuran <math> n \times m </math> dan sebuah [[Matriks simetrik\|matriks simetrik real]] tridiagonal <math>T = V^* A V</math> berukuran <math> m \times m </math>. Dalam kasus <math> m = n </math>, maka <math> V </math> akan berupa [[matriks uniter]], dan matriks <math> A = V T V^* </math>.

	Pada prinsipnya ada empat cara untuk menulis prosedur iterasi. Paige dan karya-karya lainnya menunjukkan bahwa [[urutan operasi]] berikut adalah yang paling stabil secara numerik.:		Pada prinsipnya ada empat cara untuk menulis prosedur iterasi. Paige dan karya-karya lainnya menunjukkan bahwa [[urutan operasi]] berikut adalah yang paling stabil secara numerik.<ref name="CW1985">Cullum. ''Lanczos Algorithms for Large Symmetric Eigenvalue Computations''. Vol. 1. ISBN 0-8176-3058-9.</ref><ref name="Saad1992">Yousef Saad. [http://www-users.cs.umn.edu/~saad/books.html Numerical Methods for Large Eigenvalue Problems]. 1992-06-22. ISBN 0-470-21820-7.</ref>:

	# Anggap <math>v_1 \in \mathbb{C}^n</math> sebagai sebarang vektor dengan [[norma Euklidean]] <math> 1 </math>		# Anggap <math>v_1 \in \mathbb{C}^n</math> sebagai sebarang vektor dengan [[norma Euklidean]] <math> 1 </math>
Baris 45:		Baris 45:
	* [[Matriks tridiagonal\|Rekursi kontinu]] (''continuant recursion'') memungkinkan komputasi [[polinomial karakteristik]] dengan <math>O(m^2)</math> operasi, dan mengevaluasinya pada sebuah titik dalam <math> O(m) </math> operasi.		* [[Matriks tridiagonal\|Rekursi kontinu]] (''continuant recursion'') memungkinkan komputasi [[polinomial karakteristik]] dengan <math>O(m^2)</math> operasi, dan mengevaluasinya pada sebuah titik dalam <math> O(m) </math> operasi.
	* [[Algoritme nilai eigen bagi-dan-taklukkan\|Algoritma nilai eigen bagi-dan-taklukkan]] (''divide-and-conquer'') dapat digunakan untuk menghitung seluruh dekomposisi eigen dari <math> T </math> dalam <math> O(m^2) </math> operasi.		* [[Algoritme nilai eigen bagi-dan-taklukkan\|Algoritma nilai eigen bagi-dan-taklukkan]] (''divide-and-conquer'') dapat digunakan untuk menghitung seluruh dekomposisi eigen dari <math> T </math> dalam <math> O(m^2) </math> operasi.
	* Metode Multipole Cepat (''Fast Multipole method)'' yang dapat menghitung semua nilai eigen hanya dengan <math>O(m \log m)</math> operasi.		* Metode Multipole Cepat<ref>Ed S. Coakley. ''A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices''. ''Applied and Computational Harmonic Analysis''. 2013. Vol. 34 (3). hlm. 379–414. doi:10.1016/j.acha.2012.06.003.</ref> (''Fast Multipole method)'' yang dapat menghitung semua nilai eigen hanya dengan <math>O(m \log m)</math> operasi.

	Beberapa algoritma dekomposisi eigen yang umum, terutama [[algoritme QR\|algoritma QR]], diketahui konvergen lebih cepat pada kasus matriks tridiagonal daripada pada matriks yang umum. Kompleksitas asimtotik QR untuk matriks tridiagonal adalah <math>O(m^2)</math>, sama seperti untuk algoritma bagi-dan-taklukkan (meskipun faktor konstantanya mungkin berbeda). Mengingat semua vektor eigen memiliki <math> m^2 </math> total elemen, algoritma ini optimal secara asimtotik. Bahkan untuk algoritma yang tingkat konvergensinya tidak terpengaruh oleh transformasi uniter (seperti [[metode daya]] dan [[iterasi invers]]), dapat menikmati manfaat kinerja ketika diterapkan ke matriks tridiagonal <math> T </math> daripada matriks asli <math>A</math>. Karena struktur <math> T </math> yang sangat rongga dengan semua elemen bukan nol dalam posisi yang dapat diprediksi, hal ini memungkinkan penyimpanan yang ringkas dengan kinerja yang sangat baik jika dibandingkan dengan menggunakan [[Tembolok (komputer)\|tembolok (''caching'')]]. Selain itu, <math> T </math> berupa matriks [[bilangan real \|real]] dengan semua vektor eigen dan nilai eigen berupa real, sedangkan matriks <math> A </math> secara umum mungkin memiliki elemen kompleks dan vektor eigen; penggunaan aritmetika real cukup untuk mencari vektor eigen dan nilai eigen dari <math>T</math>.		Beberapa algoritma dekomposisi eigen yang umum, terutama [[algoritme QR\|algoritma QR]], diketahui konvergen lebih cepat pada kasus matriks tridiagonal daripada pada matriks yang umum. Kompleksitas asimtotik QR untuk matriks tridiagonal adalah <math>O(m^2)</math>, sama seperti untuk algoritma bagi-dan-taklukkan (meskipun faktor konstantanya mungkin berbeda). Mengingat semua vektor eigen memiliki <math> m^2 </math> total elemen, algoritma ini optimal secara asimtotik. Bahkan untuk algoritma yang tingkat konvergensinya tidak terpengaruh oleh transformasi uniter (seperti [[metode daya]] dan [[iterasi invers]]), dapat menikmati manfaat kinerja ketika diterapkan ke matriks tridiagonal <math> T </math> daripada matriks asli <math>A</math>. Karena struktur <math> T </math> yang sangat rongga dengan semua elemen bukan nol dalam posisi yang dapat diprediksi, hal ini memungkinkan penyimpanan yang ringkas dengan kinerja yang sangat baik jika dibandingkan dengan menggunakan [[Tembolok (komputer)\|tembolok (''caching'')]]. Selain itu, <math> T </math> berupa matriks [[bilangan real \|real]] dengan semua vektor eigen dan nilai eigen berupa real, sedangkan matriks <math> A </math> secara umum mungkin memiliki elemen kompleks dan vektor eigen; penggunaan aritmetika real cukup untuk mencari vektor eigen dan nilai eigen dari <math>T</math>.
Baris 56:		Baris 56:
	Algoritma Lanczos sangat menarik karena perkalian dengan <math> A\, </math> adalah satu-satunya operasi linier berskala besar. Karena mesin pengambilan teks jangka berbobot hanya menerapkan operasi ini, algoritma Lanczos dapat diterapkan secara efisien ke dokumen teks (lihat [[Pengindeksan Semantik Laten]]). Vektor eigen juga penting untuk metode peringkat skala besar seperti [[Algoritma HITS]] yang dikembangkan oleh [[Jon Kleinberg]], atau [[PageRank]] yang digunakan oleh [[Google]].		Algoritma Lanczos sangat menarik karena perkalian dengan <math> A\, </math> adalah satu-satunya operasi linier berskala besar. Karena mesin pengambilan teks jangka berbobot hanya menerapkan operasi ini, algoritma Lanczos dapat diterapkan secara efisien ke dokumen teks (lihat [[Pengindeksan Semantik Laten]]). Vektor eigen juga penting untuk metode peringkat skala besar seperti [[Algoritma HITS]] yang dikembangkan oleh [[Jon Kleinberg]], atau [[PageRank]] yang digunakan oleh [[Google]].

	Algoritma Lanczos juga digunakan dalam [[Fisika Materi Terkondensasi]] sebagai metode untuk menyelesaikan [[matriks Hamilton \| Hamiltonians]] dari [[Materi berkorelasi kuat \| sistem elektron berkorelasi kuat]], serta dalam kode [[model cangkang nuklir \| model cangkang]] pada [[fisika nuklir]].		Algoritma Lanczos juga digunakan dalam [[Fisika Materi Terkondensasi]] sebagai metode untuk menyelesaikan [[matriks Hamilton \| Hamiltonians]] dari [[Materi berkorelasi kuat \| sistem elektron berkorelasi kuat]],<ref>HY Chen. ''Disorder-induced zero-bias anomaly in the Anderson-Hubbard model: Numerical and analytical calculations''. ''Physical Review B''. July 2011. Vol. 84 (4). hlm. 045113. doi:10.1103/PhysRevB.84.045113.</ref> serta dalam kode [[model cangkang nuklir \| model cangkang]] pada [[fisika nuklir]].<ref>Noritaka Shimizu. ''Nuclear shell-model code for massive parallel computation, "KSHELL"''. 21 October 2013.</ref>

	== Implementasi ==		== Implementasi ==
	[[Perpustakaan Numerik NAG \| Perpustakaan NAG]] berisi beberapa rutinitas untuk solusi sistem linear skala besar dan masalah eigen yang menggunakan algoritma Lanczos.		[[Perpustakaan Numerik NAG \| Perpustakaan NAG]] berisi beberapa rutinitas<ref>The Numerical Algorithms Group. [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html Keyword Index: Lanczos]. ''NAG Library Manual, Mark 23''.</ref> untuk solusi sistem linear skala besar dan masalah eigen yang menggunakan algoritma Lanczos.

	[[MATLAB]] dan [[GNU Octave]] hadir dengan ARPACK bawaan. Baik matriks yang tersimpan dan implisit dapat dianalisis melalui fungsi '' eigs() '' ([http://www.mathworks.com/help/techdoc/ref/eigs.html Matlab]/[https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs Octave]).		[[MATLAB]] dan [[GNU Octave]] hadir dengan ARPACK bawaan. Baik matriks yang tersimpan dan implisit dapat dianalisis melalui fungsi '' eigs() '' ([http://www.mathworks.com/help/techdoc/ref/eigs.html Matlab]/[https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs Octave]).

	Implementasi Matlab dari algoritma Lanczos (masalah presisi catatan) tersedia sebagai bagian dari [https://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. The [[GraphLab]] perpustakaan pemfilteran kolaboratif menggabungkan implementasi paralel skala besar dari algoritma Lanczos (dalam C ++) untuk multicore.		Implementasi Matlab dari algoritma Lanczos (masalah presisi catatan) tersedia sebagai bagian dari [https://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. The [[GraphLab]]<ref>[http://www.graphlab.ml.cmu.edu/pmf.html GraphLab]</ref> perpustakaan pemfilteran kolaboratif menggabungkan implementasi paralel skala besar dari algoritma Lanczos (dalam C ++) untuk multicore.

	[http://www.cs.wm.edu/~andreas/software/ PRIMME] perpustakaan juga menerapkan algoritma seperti Lanczos.		[http://www.cs.wm.edu/~andreas/software/ PRIMME] perpustakaan juga menerapkan algoritma seperti Lanczos.

	~~== Referensi ==~~


	== Bacaan lebih lanjut ==		== Bacaan lebih lanjut ==
			*
	*		*
	*
			== Referensi ==
			<references />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	~~Artikel~~ ini diadaptasi ~~dalam mode teks~~ dari		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Lanczos&oldid=29187963 Wikipedia bahasa Indonesia], revisi 29187963 (2026-05-02T15:36:03Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.
	[https://id.wikipedia.org/w/index.php?title=~~Algoritma_Lanczos~~&oldid=29187963 Wikipedia bahasa Indonesia],
	revisi 29187963 (2026-05-02T15:36:03Z).		<!-- WIKI_UNISSULA_PRESENTATION_V4 -->
	~~Gambar, media, infobox, templat navigasi~~, ~~dan kategori sumber~~
	~~tidak diimpor ke Wiki Unissula.~~
	~~Atribusi dan~~ lisensi ~~mengikuti ketentuan~~ Creative Commons
	Atribusi-BerbagiSerupa (CC BY-SA) ~~pada sumber Wikipedia~~.

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187963; atribusi sumber disertakan.

2026-08-23T02:25:21Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187963; atribusi sumber disertakan.

Halaman baru

'''Algoritma Lanczos''' adalah [[algoritme|algoritma]] iteratif adaptasi dari metode daya (''power method'') untuk menemukan <math>m</math> nilai dan vektor eigen yang "paling berguna" (umumnya yang tertinggi/terendah) dari sebuah [[matriks Hermite]] berukuran <math>n \times n</math>, dengan <math>m</math> tidak perlu jauh lebih kecil dari <math>n</math>. Algoritma ini dirancang oleh [[Cornelius Lanczos]] pada tahun 1950. Meskipun secara prinsip metode ini efisien dalam aspek [[komputasi]], metode yang dirancang pada awalnya tidak berguna karena sifatnya yang tidak stabil secara numerik.

Pada tahun 1970, Ojalvo dan Newman menunjukkan cara membuat metode ini stabil secara numerik, dan mengaplikasikannya untuk menemukan mode getaran dari sebuah struktur teknik berukuran besar. Hal ini dicapai dengan menggunakan sebuah teknik untuk 'memurnikan' vektor-vektor Lanczos (misal dengan mengortogonalkan secara berulang setiap vektor yang baru ditemukan dengan ''semua'' vektor yang sudah ditemukan) sampai ke suatu akurasi yang diinginkan. Jika teknik tidak diterapkan, metode akan menghasilkan vektor-vektor yang sangat 'terkontaminasi' oleh vektor-vektor yang berasosiasi dengan [[frekuensi]] alami yang rendah.

Dalam karyanya, Ojalvo dan Newman juga mengusulkan cara memilih vektor awal (''starting vector;'' misalnya dengan menggunakan [[Pembangkitan bilangan acak|pembangkit bilangan acak]]), dan mengusulkan metode menentukan nilai <math> m </math> secara empiris (sebaiknya dipilih kurang lebih 1.5 kali dari banyak nilai eigen akurat yang diinginkan). Kontribusi lain diberikan oleh Paige, yang juga memberikan analisis galat untuk metode ini. Pada tahun 1988, Ojalvo memberikan sejarah yang lebih akurat dari algoritma ini, dan sebuah uji galat nilai eigen yang efisien.

== Algoritma ==
Algoritma ini memerlukan sebuah [[matriks Hermite]] <math> A </math> berukuran <math> n \times n </math>, dan secara opsional sebuah bilangan <math> m </math> yang menyatakan banyak iterasi yang diinginkan. Jika nilai <math> m </math> tidak ditentukan, umumnya diambil <math> m=n </math>. Sebenarnya, algoritma tidak memerlukan akses ke matriks secara eksplisit, melainkan sebuah fungsi <math>v \mapsto A v</math> yang menghasilkan produk [[perkalian matriks]] dengan vektor. Fungsi ini dipanggil paling banyak <math> m </math> kali. Pada proses iterasi, algoritma rentan terhadap ketidakstabilan numerik. Ketika dieksekusi dalam [[aritmetika]] non-eksak (''non-exact arithmetic''), pertimbangan-pertimbangan tambahan harus diambil untuk memastikan validitas hasil (dijelaskan di bagian selanjutnya). Di akhir iterasi, algoritma akan menghasilkan sebuah [[matriks ortonormal]] <math> V </math> berukuran <math> n \times m </math> dan sebuah [[Matriks simetrik|matriks simetrik real]] tridiagonal <math>T = V^* A V</math> berukuran <math> m \times m </math>. Dalam kasus <math> m = n </math>, maka <math> V </math> akan berupa [[matriks uniter]], dan matriks <math> A = V T V^* </math>.

Pada prinsipnya ada empat cara untuk menulis prosedur iterasi. Paige dan karya-karya lainnya menunjukkan bahwa [[urutan operasi]] berikut adalah yang paling stabil secara numerik.:

# Anggap <math>v_1 \in \mathbb{C}^n</math> sebagai sebarang vektor dengan [[norma Euklidean]] <math> 1 </math>
# Langkah awal iterasi yang disingkat:
## Tetapkan <math> w_1' = A v_1 </math>.
## Tetapkan <math> \alpha_1 = w_1'^* v_1 </math>.
## Tetapkan <math> w_1 = w_1' - \alpha_1 v_1 </math>
# Untuk nilai <math> j=2,\dots,m </math>, lakukan:
## Tetapkan <math> \beta_j = \| w_{j-1} \| </math> (juga sebuah [[norma Euklidean]]).
## Jika <math> \beta_j \neq 0 </math>, tetapkan nilai <math> v_j = w_{j-1} / \beta_j </math>. Namun jika <math> \beta_j = 0 </math>, pilih <math> v_j </math> sebagai sebarang vektor bernorma Euclidean <math> 1 </math> yang ortogonal dengan semua vektor <math> v_1,\dots,v_{j-1} </math>.
## Tetapkan <math> w_j' = A v_j </math>.
## Tetapkan <math> \alpha_j = w_j'^* v_j </math>.
## Tetapkan <math> w_j = w_j' - \alpha_j v_j - \beta_j v_{j-1} </math>.
# Bentuk matriks <math> V </math> dengan menyusun <math> v_1,\dots,v_m </math> sebagai kolom-kolomnya; dan bentuk matriks<math display="block">T = \begin{pmatrix}
\alpha_1 & \beta_2 & & & & 0 \\
\beta_2 & \alpha_2 & \beta_3 & & & \\
& \beta_3 & \alpha_3 & \ddots & & \\
& & \ddots & \ddots & \beta_{m-1} & \\
& & & \beta_{m-1} & \alpha_{m-1} & \beta_m \\
0 & & & & \beta_m & \alpha_m \\
\end{pmatrix}</math>

'''Catatan:''' <math> A v_j = w_j' = \beta_{j+1} v_{j+1} + \alpha_j v_j + \beta_j v_{j-1} </math> untuk <math> 1 < j < m </math>.

Dalam praktiknya vektor awal <math> v_1 </math> dapat dianggap sebagai argumen ''input'' tambahan dari prosedur; sedangkan <math>\beta_j=0</math> dan indikator-indikator galat numerik dapat diikutsertakan sebagai tambahan kondisi penghentian iterasi.

Tanpa menghitung perkalian matriks-vektor, setiap iterasi melakukan <math> O(n) </math> operasi aritmetika. Perkalian matriks-vektor sendiri dapat dilakukan dalam <math> O(dn) </math> operasi aritmetika, dengan <math> d </math> menyatakan rata-rata jumlah elemen bukan nol dalam sebuah baris. Dengan demikian, algoritma Lanczos memiliki total kompleksitas sebesar <math> O (dmn) </math>, atau <math> O (dn^2) </math> dalam kasus <math> m=n </math>; hal ini membuatnya bisa sangat cepat untuk [[matriks rongga]]. Skema-skema untuk meningkatkan stabilitas numerik biasanya dibandingkan dengan kinerja tinggi ini.

Vektor <math> v_j </math> disebut dengan'' vektor Lanczos''. Vektor <math> w_j'</math> tidak digunakan setelah nilai <math> w_j </math> dihitung, dan vektor <math> w_j </math> tidak digunakan setelah <math> v_{j+1} </math> dihitung. Hal ini memungkinkan untuk menggunakan penyimpanan yang sama untuk ketiga vektor tersebut. Begitu juga jika kita hanya ingin mencari matriks tridiagonal <math> T </math>, proses iterasi tidak memerlukan <math> v_{j-1} </math> setelah menghitung <math> w_j </math>; meskipun beberapa skema untuk meningkatkan stabilitas numerik akan membutuhkan vektor ini nantinya. Terkadang vektor-vektor Lanczos yang berikutnya dihitung ulang dari <math>v_1</math> jika diperlukan.

== Aplikasi untuk masalah eigen ==
Algoritma Lanczos paling sering digunakan dalam konteks menemukan [[nilai eigen]] dan [[vektor eigen]] dari sebuah matriks. Namun berbeda dengan[[ diagonalisasi matriks]] yang menghasilkan vektor-vektor eigen dan nilai-nilai eigen terlihat jelas dari pemeriksaan, tridiagonalisasi yang dilakukan algoritma Lanczos memerlukan langkah-langkah tambahan yang nontrivial bahkan untuk menghitung satu nilai atau vektor eigen. Meskipun demikian, menerapkan algoritma Lanczos sering kali merupakan langkah signifikan yang dalam menghitung dekomposisi eigen. Jika <math>\lambda</math> adalah nilai eigen dari <math> A </math> dan <math>x</math> adalah vektor eigen dari <math> T </math> (sehingga <math> T x = \lambda x </math>), maka <math> y = V x </math> adalah vektor eigen yang bersesuaian dari <math>A</math>; karena <math display="block"> A y = A V x = V T V^* V x = V T I x = V T x = V (\lambda x) = \lambda V x = \lambda y.</math>Hal ini mengartikan algoritma Lanczos mengubah masalah dekomposisi eigen matriks <math> A </math> menjadi masalah dekomposisi eigen matriks <math> T </math>.

Terdapat sejumlah algoritma khusus untuk memroses matriks tridiagonal, sering kali dengan kompleksitas komputasi yang lebih baik daripada algoritma yang umum. Misalkan <math>T</math> adalah matriks simetris tridiagonal berukuran <math>m \times m</math>. Beberapa algoritma tersebut diantaranya:

* [[Matriks tridiagonal|Rekursi kontinu]] (''continuant recursion'') memungkinkan komputasi [[polinomial karakteristik]] dengan <math>O(m^2)</math> operasi, dan mengevaluasinya pada sebuah titik dalam <math> O(m) </math> operasi.
* [[Algoritme nilai eigen bagi-dan-taklukkan|Algoritma nilai eigen bagi-dan-taklukkan]] (''divide-and-conquer'') dapat digunakan untuk menghitung seluruh dekomposisi eigen dari <math> T </math> dalam <math> O(m^2) </math> operasi.
* Metode Multipole Cepat (''Fast Multipole method)'' yang dapat menghitung semua nilai eigen hanya dengan <math>O(m \log m)</math> operasi.

Beberapa algoritma dekomposisi eigen yang umum, terutama [[algoritme QR|algoritma QR]], diketahui konvergen lebih cepat pada kasus matriks tridiagonal daripada pada matriks yang umum. Kompleksitas asimtotik QR untuk matriks tridiagonal adalah <math>O(m^2)</math>, sama seperti untuk algoritma bagi-dan-taklukkan (meskipun faktor konstantanya mungkin berbeda). Mengingat semua vektor eigen memiliki <math> m^2 </math> total elemen, algoritma ini optimal secara asimtotik. Bahkan untuk algoritma yang tingkat konvergensinya tidak terpengaruh oleh transformasi uniter (seperti [[metode daya]] dan [[iterasi invers]]), dapat menikmati manfaat kinerja ketika diterapkan ke matriks tridiagonal <math> T </math> daripada matriks asli <math>A</math>. Karena struktur <math> T </math> yang sangat rongga dengan semua elemen bukan nol dalam posisi yang dapat diprediksi, hal ini memungkinkan penyimpanan yang ringkas dengan kinerja yang sangat baik jika dibandingkan dengan menggunakan [[Tembolok (komputer)|tembolok (''caching'')]]. Selain itu, <math> T </math> berupa matriks [[bilangan real |real]] dengan semua vektor eigen dan nilai eigen berupa real, sedangkan matriks <math> A </math> secara umum mungkin memiliki elemen kompleks dan vektor eigen; penggunaan aritmetika real cukup untuk mencari vektor eigen dan nilai eigen dari <math>T</math>.

Jika <math>n</math> sangat besar, nilai <math> m </math> dapat dikurangi sehingga matriks <math> T </math> yang dihasilkan masih memiliki ukuran yang dapat dikelola. Pengurangan ini masih memungkinkan untuk menemukan nilai eigen dan vektor eigen yang ekstrem dari <math>A</math>. Dalam keadaan <math>m \ll n</math>, algoritma Lanczos dapat dianggap sebagai skema [[kompresi lossy|kompresi ''lossy'']] untuk [[matriks Hermite]], yang mengutamakan meyimpanan nilai-nilai eigen ekstrem.

Kombinasi kinerja yang baik untuk [[matriks rongga]] dan kemampuan untuk menghitung beberapa (tanpa menghitung semua) nilai eigen adalah alasan utama untuk memilih menggunakan algoritma Lanczos.

== Aplikasi ==
Algoritma Lanczos sangat menarik karena perkalian dengan <math> A\, </math> adalah satu-satunya operasi linier berskala besar. Karena mesin pengambilan teks jangka berbobot hanya menerapkan operasi ini, algoritma Lanczos dapat diterapkan secara efisien ke dokumen teks (lihat [[Pengindeksan Semantik Laten]]). Vektor eigen juga penting untuk metode peringkat skala besar seperti [[Algoritma HITS]] yang dikembangkan oleh [[Jon Kleinberg]], atau [[PageRank]] yang digunakan oleh [[Google]].

Algoritma Lanczos juga digunakan dalam [[Fisika Materi Terkondensasi]] sebagai metode untuk menyelesaikan [[matriks Hamilton | Hamiltonians]] dari [[Materi berkorelasi kuat | sistem elektron berkorelasi kuat]], serta dalam kode [[model cangkang nuklir | model cangkang]] pada [[fisika nuklir]].

== Implementasi ==
[[Perpustakaan Numerik NAG | Perpustakaan NAG]] berisi beberapa rutinitas untuk solusi sistem linear skala besar dan masalah eigen yang menggunakan algoritma Lanczos.

[[MATLAB]] dan [[GNU Octave]] hadir dengan ARPACK bawaan. Baik matriks yang tersimpan dan implisit dapat dianalisis melalui fungsi '' eigs() '' ([http://www.mathworks.com/help/techdoc/ref/eigs.html Matlab]/[https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs Octave]).

Implementasi Matlab dari algoritma Lanczos (masalah presisi catatan) tersedia sebagai bagian dari [https://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. The [[GraphLab]] perpustakaan pemfilteran kolaboratif menggabungkan implementasi paralel skala besar dari algoritma Lanczos (dalam C ++) untuk multicore.

[http://www.cs.wm.edu/~andreas/software/ PRIMME] perpustakaan juga menerapkan algoritma seperti Lanczos.

== Referensi ==

== Bacaan lebih lanjut ==
*
*

== Sumber dan atribusi ==

Artikel ini diadaptasi dalam mode teks dari
[https://id.wikipedia.org/w/index.php?title=Algoritma_Lanczos&oldid=29187963 Wikipedia bahasa Indonesia],
revisi 29187963 (2026-05-02T15:36:03Z).
Gambar, media, infobox, templat navigasi, dan kategori sumber
tidak diimpor ke Wiki Unissula.
Atribusi dan lisensi mengikuti ketentuan Creative Commons
Atribusi-BerbagiSerupa (CC BY-SA) pada sumber Wikipedia.