Sturms teoremi - Sturms theorem - Wikipedia

İçinde matematik, Sturm dizisi bir tek değişkenli polinom p ile ilişkili bir polinom dizisidir p ve türevinin bir türevi Polinomlar için Öklid algoritması. Sturm teoremi farklı sayısını ifade eder gerçek kökler nın-nin p bir Aralık aralığın sınırlarında Sturm dizisinin değerlerinin işaretlerinin değişiklik sayısı açısından. Tüm reel sayıların aralığına uygulandığında, toplam gerçek kök sayısını verir. p.[1]

Oysa cebirin temel teoremi kolayca genel sayısını verir karmaşık ile sayılan kökler çokluk, bunların hesaplanması için bir prosedür sağlamaz. Sturm teoremi, farklı gerçek köklerin sayısını sayar ve bunları aralıklarla bulur. Bazı kökleri içeren aralıkları alt bölümlere ayırarak, kökleri her biri tam olarak bir kök içeren rastgele küçük aralıklara ayırabilir. Bu en eskiyi verir gerçek kök izolasyonu algoritma ve keyfi hassasiyet kök bulma algoritması tek değişkenli polinomlar için.

Üzerinden bilgi işlem için gerçekler Sturm teoremi, diğer yöntemlere göre daha az etkilidir. Descartes'ın işaretler kuralı. Ancak, her gerçek kapalı alan ve bu nedenle, teorik çalışma için temel kalır. hesaplama karmaşıklığı nın-nin karar verebilirlik ve nicelik belirteci eliminasyonu içinde birinci dereceden teori gerçek sayılar.

Sturm dizisi ve Sturm teoremi, Jacques Charles François Sturm teoremi 1829'da keşfeden.[2]

Teoremi

Sturm zinciri veya Sturm dizisi bir tek değişkenli polinom P(x) gerçek katsayılarla polinom dizisidir öyle ki

için ben ≥ 1, nerede P ' ... türev nın-nin P, ve geri kalanı Öklid bölümü nın-nin tarafından Sturm dizisinin uzunluğu en fazla P.

Sayısı işaret varyasyonları -de ξ Sturm dizisinin P gerçek sayılar dizisindeki sıfırları yok sayan işaret değişikliklerinin sayısıdır

Bu işaret varyasyonlarının sayısı burada belirtilmiştir V(ξ).

Sturm teoremi, eğer P bir karesiz polinom, farklı gerçek köklerin sayısı P içinde yarı açık aralık (a, b] dır-dir V(a) − V(b) (İşte, a ve b gerçek sayılardır öyle ki a < b).[1]

Teorem, işareti tanımlayarak sınırsız aralıklara uzanır. +∞ bir polinomun işareti olarak öncü katsayı (yani, en yüksek dereceli terimin katsayısı). Şurada: –∞ Bir polinomun işareti, çift dereceli bir polinom için önde gelen katsayısının işaretidir ve tek dereceli bir polinom için ters işarettir.

Karesiz olmayan polinom durumunda, ikisi de yoksa a ne de b birden çok köküdür p, sonra V(a) − V(b) sayısı farklı gerçek kökleri P.

Teoremin kanıtı şu şekildedir: x artar a -e bbazılarının sıfırından geçebilir (ben > 0); bu gerçekleştiğinde, işaret varyasyonlarının sayısı değişmez. Ne zaman x bir kökünden geçer işaret varyasyonlarının sayısı 1'den 0'a düşer. Bunlar, x bazı işaretlerin değişebileceği yer.

Misal

Polinom için bir aralıktaki kök sayısını bulmak istediğimizi varsayalım. . Yani

Geri kalanı Öklid bölümü nın-nin p0 tarafından p1 dır-dir ile çarparak −1 elde ederiz

.

Sonraki bölme p1 tarafından p2 ve kalanı ile çarparak −1, elde ederiz

.

Şimdi bölünüyor p2 tarafından p3 ve kalanı ile çarparak −1, elde ederiz

.

Bu bir sabit olduğundan, bu, Sturm dizisinin hesaplanmasını bitirir.

Gerçek kök sayısını bulmak için bu polinomların işaretlerinin sıralarını şu anda değerlendirmek gerekir −∞ ve sırasıyla (+, −, +, +, −) ve (+, +, +, −, −). Böylece

bunu gösterir p iki gerçek köke sahiptir.

Bu, not edilerek doğrulanabilir p(x) olarak çarpanlara ayrılabilir (x2 − 1)(x2 + x + 1), ilk faktörün köklerinin olduğu yer −1 ve 1ve ikinci faktörün gerçek kökleri yoktur. Bu son iddia, ikinci dereceden formül ve ayrıca işaret dizilerini veren Sturm teoreminden (+, –, –) -de −∞ ve (+, +, –) -de +∞.

Genelleme

Sturm dizileri iki yönde genelleştirilmiştir. Dizideki her bir polinomu tanımlamak için Sturm, dizinin geri kalanının negatifini kullandı. Öklid bölümü önceki iki tanesinden. Teorem, geri kalanın negatifini çarpımı veya bölümü ile pozitif bir sabit veya bir polinomun karesiyle değiştirirse doğru kalır. İkinci polinomun birincinin türevi olmadığı dizileri dikkate almak da (aşağıya bakınız) faydalıdır.

Bir genelleştirilmiş Sturm dizisi gerçek katsayıları olan sonlu bir polinom dizisidir

öyle ki

  • dereceler ilkinden sonra düşüyor: için ben = 2, ..., m;
  • herhangi bir gerçek köke sahip değildir veya gerçek köklerinin yakınında işaret değişikliği yoktur.
  • Eğer Pben(ξ) = 0 için 0 < ben < m ve ξ gerçek bir sayı, o zaman Pben −1 (ξ) Pben + 1(ξ) < 0.

Son koşul, iki ardışık polinomun herhangi bir ortak gerçek köke sahip olmadığı anlamına gelir. Özellikle, orijinal Sturm dizisi genelleştirilmiş bir Sturm dizisidir, eğer polinomun çoklu gerçek kökü yoksa (aksi halde Sturm dizisinin ilk iki polinomunun ortak bir kökü varsa).

Orijinal Sturm dizisini Öklid bölünmesiyle hesaplarken, hiçbir zaman negatif olmayan bir faktörü olan bir polinomla karşılaşılabilir veya . Bu durumda, hesaplamaya, polinomun bölümü negatif olmayan faktör ile değiştirilmesiyle devam ederse, Sturm teoreminin kanıtı hala geçerli olduğundan, gerçek köklerin sayısını hesaplamak için de kullanılabilen genelleştirilmiş bir Sturm dizisi elde edilir ( üçüncü koşul nedeniyle). Bu, bazen hesaplamayı basitleştirebilir, ancak bu tür negatif olmayan faktörleri bulmak genellikle zordur, eşit güçler dışında x.

Sözde kalan dizilerin kullanımı

İçinde bilgisayar cebiri tam sayı katsayılarına sahip olduğu düşünülen polinomlar, tamsayı katsayılarına sahip olacak şekilde dönüştürülebilir. Tamsayı katsayıları olan bir polinomun Sturm dizisi genellikle katsayıları tamsayı olmayan polinomları içerir (yukarıdaki örneğe bakın).

Hesaplamayı önlemek için rasyonel sayılar yaygın bir yöntem, Öklid bölümü tarafından sözde bölünme bilgi işlem için polinom en büyük ortak bölenler. Bu, geri kalan dizinin değiştirilmesi anlamına gelir. Öklid algoritması tarafından sözde kalan dizi sözde kalan dizi bir dizi sabitler olacak şekilde polinomların ve öyle ki Öklid bölümünün geri kalanıdır. tarafından (Farklı türde sözde kalan diziler, seçimiyle tanımlanır. ve tipik, Öklid bölünmesi sırasında paydaları tanıtmamak için seçilir ve elde edilen kalanın katsayılarının ortak bir bölenidir; görmek Sözde kalan dizi Ayrıntılar için.) Örneğin, Öklid algoritmasının geri kalan dizisi, sözde kalan bir dizidir. her biri için benve bir polinomun Sturm dizisi, sözde kalan bir dizidir. ve her biri için ben.

Payda eklemeden tamsayı katsayıları olan polinomların en büyük ortak bölenlerini hesaplamak için çeşitli sözde kalan diziler tasarlanmıştır (bkz. Sözde kalan dizi ). Bunların tümü, işaretini seçerek genelleştirilmiş Sturm dizileri yapılabilir. burcunun tersi olmak Bu, Sturm teoreminin sözde kalan dizilerle kullanımına izin verir.

Kök izolasyonu

Gerçek katsayılara sahip bir polinom için, kök izolasyonu her gerçek kök için, bu kökü içeren ve başka hiçbir kök içermeyen bir aralık bulmaktan oluşur.

Bu, kök bulma, kök seçiminin bulunmasına izin verir ve hızlı sayısal algoritmalar için iyi bir başlangıç ​​noktası sağlar. Newton yöntemi; aynı zamanda, Newton'un yöntemi aralık dışında birleşiyormuş gibi, yanlış köke yakınsadığı sonucuna varılabileceği gibi, sonucun onaylanması için de kullanışlıdır.

Kök izolasyonu, aynı zamanda cebirsel sayılar. Cebirsel sayılarla hesaplama yapmak için yaygın bir yöntem, onları cebirsel sayının bir kök olduğu bir polinom çifti ve bir izolasyon aralığı olarak temsil etmektir. Örneğin açıkça şu şekilde temsil edilebilir:

Sturm teoremi, gerçek kökleri izole etmek için diğer yöntemlerden daha az verimli (tamsayı katsayılı polinomlar için) bir yol sağlar. Descartes'ın işaretler kuralı. Bununla birlikte, bazı durumlarda, özellikle teorik amaçlar için, örneğin gerçek cebirsel geometri içeren sonsuz küçükler.

Gerçek kökleri izole etmek için bir aralıktan başlar tüm gerçek kökleri veya ilgili kökleri içeren (genellikle, genellikle fiziksel problemlerde, yalnızca pozitif kökler ilginçtir) ve bir hesaplama ve Bu başlangıç ​​aralığını tanımlamak için, köklerin boyutuna ilişkin sınırlar kullanılabilir (bkz. Polinom köklerin özellikleri § (karmaşık) polinom kökleri üzerindeki sınırlar ). Daha sonra, bu aralığı ikiye bölerek, c ortasında Hesaplanması gerçek köklerin sayısını sağlar ve ve her alt aralıkta aynı işlem tekrarlanabilir. Bu işlem sırasında herhangi bir kök içermeyen bir aralıkla karşılaşıldığında, dikkate alınması gereken aralıklar listesinden kaldırılabilir. Tam olarak bir kök içeren bir aralıkla karşılaşıldığında, bu bir izolasyon aralığı olduğu için onu bölmeyi bırakabilir. Süreç, yalnızca ayırma aralıkları kaldığında sonunda durur.

Bu izolasyon işlemi, bir aralıktaki gerçek köklerin sayısını hesaplamak için herhangi bir yöntemle kullanılabilir. Teorik karmaşıklık analizi ve pratik deneyimler, yöntemlerin temel aldığını göstermektedir. Descartes'ın işaretler kuralı daha verimlidir. Bu, günümüzde Sturm dizilerinin nadiren kök izolasyonu için kullanıldığını izler.

Uygulama

Genelleştirilmiş Sturm dizileri, başka bir polinomun pozitif (veya negatif) olduğu bir polinomun köklerinin, bu kökü açıkça hesaplamadan sayılmasına izin verir. Birinci polinomun bir kökü için bir ayırma aralığı biliniyorsa, bu aynı zamanda, kökün daha iyi bir yaklaşımını hesaplamadan, birinci polinomun bu belirli kökünde ikinci polinomun işaretini bulmaya da izin verir.

İzin Vermek P(x) ve Q(x) gerçek katsayılara sahip iki polinom olun ki P ve Q ortak bir köke sahip değil ve P birden fazla kökü yoktur. Diğer bir deyişle, P ve P 'Q vardır coprime polinomları. Bu kısıtlama, aşağıdakilerin genelliğini gerçekten etkilemez: GCD hesaplamalar, genel durumu bu duruma indirgemeye izin verir ve bir Sturm dizisinin hesaplanmasının maliyeti, bir GCD ile aynıdır.

İzin Vermek W(a) buradaki işaret varyasyonlarının sayısını gösterir a genelleştirilmiş bir Sturm dizisinin P ve P 'Q. Eğer a < b iki gerçek sayıdır, o zaman W(a) – W(b) köklerinin sayısı P aralıkta öyle ki Q(a) > 0 eksi aynı aralıktaki kök sayısı öyle ki Q(a) < 0. Toplam kök sayısı ile birleştirildiğinde P Sturm teoremi tarafından verilen aynı aralıkta, bu, P öyle ki Q(a) > 0 ve köklerinin sayısı P öyle ki Q(a) < 0.[1]

Ayrıca bakınız

Referanslar

  1. ^ a b c (Basu, Pollack ve Roy 2006 )
  2. ^ O'Connor, John J.; Robertson, Edmund F., "Sturm teoremi", MacTutor Matematik Tarihi arşivi, St Andrews Üniversitesi.