Önkoşullandırma
Önkoşullandırma, bir doğrusal sistemi, iteratif bir çözücünün çok daha az adımda yakınsayabilmesi için daha uygun bir spektruma sahip eşdeğer bir sisteme dönüştürmektedir; bu, genellikle büyük seyrek çözücülerin performansındaki en önemli tek faktördür.
Tanım
Bir önkoşullandırıcı, bir doğrusal sisteme örtük veya açık olarak uygulanan, katsayı matrisini veya tersini yaklaşık olarak temsil eden bir matristir; bu sayede önkoşullandırılmış sistem, iteratif bir yöntemin çok daha hızlı yakınsamasına yol açan spektral özelliklere sahip olmaktadır.
Kapsam
Bu konu, özdeğerleri kümeleyen veya koşul sayısını düşüren yaklaşık bir ters matris fikrini, başlıca önkoşullandırıcı ailelerini — köşegen ve blok köşegen, eksik LU ve Cholesky çarpanlarına ayırmaları, seyrek yaklaşık ters matrisler ile alan ayrıştırma ve çoklu ızgara önkoşullandırıcıları — ve bir önkoşullandırıcının etkinliği ile oluşturma ve uygulama maliyeti arasındaki dengeyi kapsamaktadır.
Temel sorular
- Bir önkoşullandırıcı, iteratif yakınsamayı hızlandırmak için bir sistemin spektrumunu nasıl değiştirmektedir?
- Yaklaşım kalitesi ile oluşturma ve uygulama maliyeti arasındaki dengeyi sağlayan iyi bir önkoşullandırıcıyı ne iyi yapmaktadır?
- Eksik çarpanlara ayırmalar ve seyrek yaklaşık ters matrisler nasıl oluşturulmaktadır?
- Çoklu ızgara veya alan ayrıştırma yöntemleri, bağımsız çözücüler yerine ne zaman önkoşullandırıcı olarak kullanılmaktadır?
Temel kuramlar
- Spektral dönüşüm
- Matrisin tersini yaklaşık olarak temsil eden bir önkoşullandırıcı uygulamak, özdeğerleri kümelenmiş veya koşul sayısı azaltılmış bir önkoşullandırılmış operatör sağlamaktadır; Krylov yakınsaması spektruma bağlı olduğundan, bu durum iterasyon sayısını büyüklük mertebelerinde azaltabilmektedir.
- Eksik çarpanlara ayırma önkoşullandırıcıları
- Eksik LU ve eksik Cholesky çarpanlarına ayırmaları, seçilen bir seyrek desenin veya eşiğin ötesindeki dolguyu atarken yaklaşık üçgensel çarpanları hesaplayarak, matrisin etkisinin çoğunu yakalayan uygun maliyetli bir önkoşullandırıcı üretmektedir.
Mekanizmalar
Bir M önkoşullandırıcısı, M ile sistemleri çözmenin ucuz olması ve önkoşullandırılmış operatörün birim matrise yakın olup özdeğerlerini kümelemesi için seçilmektedir. Köşegen (Jacobi) önkoşullandırma sadece yeniden ölçeklendirme yapmaktadır; eksik LU veya Cholesky çarpanlarına ayırmaları, eleme sırasında küçük veya desen dışı girdileri atarak yaklaşık seyrek üçgensel çarpanlar oluşturmaktadır; seyrek yaklaşık ters matrisler ise tersi yaklaşık olarak temsil eden seyrek bir M matrisini doğrudan oluşturarak sadece matris-vektör çarpımlarının gerekli olmasını sağlamaktadır. Daha güçlü önkoşullandırıcılar, her iterasyonda bir çoklu ızgara döngüsü veya bir alan ayrıştırma çözümü uygulamaktadır. Her durumda, önkoşullandırıcı bir Krylov yönteminin her adımında uygulanmakta ve tasarımı, tersi ne kadar iyi yaklaştırdığı ile oluşturma ve uygulama maliyeti arasındaki dengeyi sağlamaktadır.
Klinik önem
Önkoşullandırma, kısmi diferansiyel denklem (PDE) ayrıklaştırmalarından ve büyük ölçekli optimizasyondan kaynaklanan muazzam kötü koşullu sistemleri çözmek için belirleyicidir; doğru önkoşullandırıcı, duraklayan bir iterasyonu birkaç adımda yakınsayan bir iterasyona dönüştürebilmekte ve önkoşullandırıcıları seçmek ve ayarlamak, hesaplamalı bilim ve mühendislik yazılımlarında merkezi bir pratik endişe kaynağı olmaktadır.
Tarihçe
Önkoşullandırma, 1970'lerden itibaren Krylov yöntemleriyle birlikte gelişmiş, eksik çarpanlara ayırmalar 1977'de Meijerink ve van der Vorst tarafından tanıtılmış ve o zamandan beri geniş bir cebirsel ve çok seviyeli önkoşullandırıcı yelpazesi geliştirilmiştir; günümüzde, çözücü performansında Krylov yönteminin kendisinin seçiminden genellikle daha önemli olduğu kabul edilmektedir.
Öne çıkan isimler
- Yousef Saad
- Michele Benzi
- Henk van der Vorst
- Olof Widlund
İlgili konular
Temel eserler
- saad2003
- benzi2002
Sıkça sorulan sorular
- İyi bir önkoşullandırıcıyı ne iyi yapmaktadır?
- İyi bir önkoşullandırıcı, matrisin tersini yakından yaklaşık olarak temsil ederek önkoşullandırılmış sistemin iteratif yöntem için kolay olmasını sağlamakta, ancak oluşturulması ve uygulanması ucuz olmaktadır. Buradaki sanat, bu çelişkili hedefleri dengelemektir: daha doğru bir önkoşullandırıcı adım başına daha fazla maliyetli olmakla birlikte daha az adım gerektirmektedir.
- Bir çözücü önkoşullandırıcı olarak kullanılabilir mi?
- Evet. Bir çoklu ızgara döngüsü veya bir alan ayrıştırma çözümü, sıklıkla bir Krylov yönteminin içinde önkoşullandırıcı olarak kullanılmakta, Krylov iterasyonunun sağlamlığını iç çözücünün hızlı hata azaltmasıyla birleştirmektedir.