Slayt 3

Horner Williams George (1786-22.9.1837) - İngiliz matematikçi. Bristol'da doğdum. Orada okudu ve çalıştı, ardından Bath'taki okullarda çalıştı. Cebirle ilgili temel çalışmalar. 1819'da Bir polinomun gerçek köklerinin yaklaşık olarak hesaplanması için şu anda Ruffini-Horner yöntemi olarak adlandırılan bir yöntem yayınladı (bu yöntem, 13. yüzyılda Çinliler tarafından biliniyordu). Horner'dan sonra.

Slayt 4

HORNER ŞEMASI

Tamamlanmamış bölümün ve geri kalanın katsayılarının bölünen polinomun katsayılarıyla ve aşağıdaki formüllerle ilişkili olduğu gerçeğine dayanan, n'inci dereceden bir polinomu doğrusal bir binom - a'ya bölme yöntemi:

Slayt 5

Horner şemasına göre hesaplamalar tabloya yerleştirilmiştir:

Örnek 1. Böl Kısmi bölüm x3-x2+3x - 13 ve kalan 42=f(-3)'tür.

Slayt 6

Bu yöntemin temel avantajı, gösterimin kompaktlığı ve bir polinomu hızlı bir şekilde binoma bölme yeteneğidir. Aslında Horner'ın şeması, gruplama yöntemini kaydetmenin başka bir biçimidir, ancak ikincisinden farklı olarak tamamen görsel değildir. Cevap (çarpanlara ayırma) burada kendiliğinden elde edilir ve onu elde etme sürecini görmüyoruz. Horner'ın planının kesin bir şekilde doğrulanmasına girişmeyeceğiz, yalnızca nasıl çalıştığını göstereceğiz.

Slayt 7

Örnek 2.

P(x)=x4-6x3+7x-392 polinomunun x-7'ye bölünebileceğini kanıtlayalım ve bölmenin bölümünü bulalım. Çözüm. Horner'ın şemasını kullanarak P(7)'yi buluyoruz: Buradan P(7)=0 elde ediyoruz, yani. bir polinomu x-7'ye böldüğümüzde kalan sıfıra eşittir ve dolayısıyla P(x) polinomu (x-7)'nin katıdır. Ayrıca tablonun ikinci satırındaki sayılar, polinomun katsayılarıdır. P(x)'in (x-7)'ye bölümü, dolayısıyla P(x)=(x-7)(x3+x2+7x+56).

Slayt 8

x3 – 5x2 – 2x + 16 polinomunu çarpanlarına ayırın.

Bu polinomun tamsayı katsayıları vardır. Eğer bir tamsayı bu polinomun kökü ise, o zaman 16 sayısının bölenidir. Dolayısıyla, eğer belirli bir polinomun tamsayı kökleri varsa, bunlar yalnızca ±1 sayıları olabilir; ±2; ±4; ±8; ±16. Doğrudan doğrulamayla 2 sayısının bu polinomun kökü olduğuna ikna olduk, yani x3 – 5x2 – 2x + 16 = (x – 2)Q(x), burada Q(x) ikinci dereceden bir polinomdur

Slayt 9

Ortaya çıkan 1, −3, −8 sayıları orijinal polinomun x – 2'ye bölünmesiyle elde edilen polinomun katsayılarıdır. Bu da bölme işleminin sonucunun şu şekilde olduğu anlamına gelir: 1 x2 + (–3)x + ( –8) = x2 – 3x – 8. Bölme sonucu elde edilen bir polinomun derecesi her zaman orijinalinin derecesinden 1 eksiktir. Yani: x3 – 5x2 – 2x + 16 = (x – 2)(x2 – 3x – 8).

Horner William George () İngiliz matematikçi. Ana araştırma cebirsel denklemler teorisi ile ilgilidir. Herhangi bir dereceden denklemlerin yaklaşık çözümü için bir yöntem geliştirildi. 1819'da cebir için bir polinomu binomiye (x – a) bölmeye yönelik önemli bir yöntem (Horner şeması) tanıttı.

Horner şeması için formüllerin türetilmesi Polinom f(x)'i kalanla bir binom (x-c) ile bölmek, f(x)=(x-c)q(x)+ olacak şekilde bir q(x) polinomu ve bir r sayısı bulmak anlamına gelir r Bu eşitliği ayrıntılı olarak yazın: f 0 x n + f 1 x n-1 + f 2 x n-2 + …+f n-1 x + f n = =(x-c) (q 0 x n-1 + q 1 x n-2 + q 2 x n-3 +…+ q n-2 x + q n-1)+r Katsayıları aynı kuvvetlere eşitleyelim: x n: f 0 = q 0 => q 0 = f 0 x n-1: f 1 = q 1 - c q 0 => q 1 = f 1 + c q 0 x n-2: f 2 = q 2 - c q 1 => q 2 = f 2 + c q 1 … X 0: f n = q n - c q n-1 => q n = f n + c q n-1 q 0 = f 0 x n-1: f 1 = q 1 - c q 0 => q 1 = f 1 + c q 0 x n-2: f 2 = q 2 - c q 1 => q 2 = f 2 + c q 1 … X 0: f n = q n - c q n-1 => q n = f n + c q n-1">

Horner şemasının işleyişinin gösterilmesi Horner şemasını kullanarak, f(x) = x 3 - 5x polinomunu kalanıyla birlikte binom x-2'ye böleriz. Orijinal polinom f 0, f 1'in katsayılarını yazarız. f 2, f 3. f0f0 f1f1 f2f2 f3f c 2 (x-c)'ye bölersek, soldan ikinci satıra c yazarız. Geri kalan r için boş hücreler hazırlayın ve tamamlanmamış bölümün katsayıları q 0, q 1 ,q 2 q0q0 q1q1 q2q2 r g 0:=f 0 =1 1 g 1:= c *g 0 + f 1 * + =2 * 1 + (-5)=-3 g 2:= s *g 1 + f 2 =2 * (-3) + 0=-6 * + r:= s *g 2 + f 3 =2 * (-6) + 8= * + -4 Cevap: g(x)=x 2 -3x -6; r= -4. f(x)= (x-2)(x 2 -3x-6)-4

Bir polinomun bir binomun kuvvetleri cinsinden genişletilmesi Horner şemasını kullanarak, f(x)=x 3 +3x 2 -2x+4 polinomunu bir binomun (x+2) kuvvetleri cinsinden genişletiyoruz f(x)=x 3 +3x 2 -2x+4 =(x +2)(x 2 +x-4) f(x)=x 3 +3x 2 -2x+4= (x+2)((x-1)(x+2) -2) f(x)= x 3 +3x 2 -2x+4= (((1*(x+2)-3)(x+2)-2)(x+2)) f(x) = x 3 +3x 2 -2x+ 4 = (x+2)(x 2 +x-4)+12 = (x+2)((x-1)(x+2)-2)+12 = = (( (1*(x+2 )-3)(x+2)-2)(x+2))+12 = (x+2) 3 -3(x+2) 2 -2(x+2)+ 12

Ödev 1. f(x)=2x 5 -x 4 -3x 3 +x-3'ü x-3'e bölün; 2. Horner şemasını kullanarak, f(x)=x 4 -2x 3 +2x 2 -x-6 polinomunun tamsayı köklerini bulun (*Not: tamsayı katsayılı bir polinomun tamsayı kökleri, bölenler arasında aranmalıdır) serbest terimin ±1;±2;± 3;±6)

Horner şeması - bir polinomu bölme yöntemi

$$P_n(x)=\sum\limits_(i=0)^(n)a_(i)x^(n-i)=a_(0)x^(n)+a_(1)x^(n-1 )+a_(2)x^(n-2)+\ldots+a_(n-1)x+a_n$$

$x-a$ binomunda. İlk satırı belirli bir polinomun katsayılarını içeren bir tabloyla çalışmanız gerekecek. İkinci satırın ilk elemanı $x-a$ binomundan alınan $a$ sayısı olacaktır:

n'inci dereceden bir polinomu $x-a$ binomuna böldükten sonra, derecesi orijinalden bir eksik olan bir polinom elde ederiz; $n-1$'a eşittir. Horner'ın planının doğrudan uygulamasını örneklerle göstermek en kolay yoldur.

Örnek No.1

Horner'ın şemasını kullanarak $5x^4+5x^3+x^2-11$'ı $x-1$'a bölün.

İki satırlık bir tablo yapalım: İlk satıra $x$ değişkeninin azalan kuvvetlerine göre düzenlenmiş $5x^4+5x^3+x^2-11$ polinomunun katsayılarını yazıyoruz. Bu polinomun birinci dereceden $x$ içermediğini unutmayın; $x$'ın birinci kuvvetinin katsayısı 0'dır. $x-1$'a böldüğümüz için ikinci satıra bir tane yazıyoruz:

İkinci satırdaki boş hücreleri doldurmaya başlayalım. İkinci satırın ikinci hücresine $5$ sayısını yazıyoruz ve onu ilk satırın karşılık gelen hücresinden hareket ettiriyoruz:

Bir sonraki hücreyi şu prensibe göre dolduralım: $1\cdot 5+5=10$:

İkinci satırın dördüncü hücresini de aynı şekilde dolduralım: $1\cdot 10+1=11$:

Beşinci hücre için şunu elde ederiz: $1\cdot 11+0=11$:

Ve son olarak, son altıncı hücre için şunu elde ederiz: $1\cdot 11+(-11)=0$:

Sorun çözüldü, geriye sadece cevabı yazmak kalıyor:

Gördüğünüz gibi ikinci satırda yer alan (bir ile sıfır arasında) sayılar $5x^4+5x^3+x^2-11$'ın $x-1$'a bölünmesiyle elde edilen polinomun katsayılarıdır. Doğal olarak, orijinal $5x^4+5x^3+x^2-11$ polinomunun derecesi dörde eşit olduğundan, elde edilen $5x^3+10x^2+11x+11$ polinomunun derecesi şöyle olur: bir tane daha az, yani . üçe eşittir. İkinci satırdaki son sayı (sıfır), $5x^4+5x^3+x^2-11$ polinomunun $x-1$'a bölünmesinden kalan kısım anlamına gelir. Bizim durumumuzda kalan sıfırdır, yani. polinomlar eşit olarak bölünebilir. Bu sonuç şu şekilde de karakterize edilebilir: $5x^4+5x^3+x^2-11$ polinomunun $x=1$ noktasındaki değeri sıfıra eşittir.

Sonuç şu şekilde de formüle edilebilir: $5x^4+5x^3+x^2-11$ polinomunun $x=1$ noktasındaki değeri sıfıra eşit olduğundan, bu durumda birlik polinomun köküdür $5x^4+5x^3+ x^2-11$.

Örnek No.2

$x^4+3x^3+4x^2-5x-47$ polinomunu Horner şemasını kullanarak $x+3$'a bölün.

Hemen $x+3$ ifadesinin $x-(-3)$ biçiminde temsil edilmesi gerektiğini şart koşalım. Horner'ın planı tam olarak -3$'ı içerecek. Orijinal $x^4+3x^3+4x^2-5x-47$ polinomunun derecesi dörde eşit olduğundan, bölme sonucunda üçüncü dereceden bir polinom elde ederiz:

Sonuç şu anlama geliyor

$$x^4+3x^3+4x^2-5x-47=(x+3)(x^3+0\cdot x^2 +4x-17)+4=(x+3)(x^ 3+4x-17)+4$$

Bu durumda $x^4+3x^3+4x^2-5x-47$ $x+3$'a bölündüğünde kalan $4$ olur. Veya aynı olan, $x=-3$ için $x^4+3x^3+4x^2-5x-47$ polinomunun değeri $4$'a eşittir. Bu arada, verilen polinomun içine doğrudan $x=-3$ yazarak bunu tekrar kontrol etmek kolaydır:

$$x^4+3x^3+4x^2-5x-47=(-3)^4+3 \cdot (-3)^3-5 \cdot (-3)-47=4.$$

Onlar. Bir değişkenin belirli bir değeri için bir polinomun değerini bulmanız gerekiyorsa Horner şeması kullanılabilir. Amacımız bir polinomun tüm köklerini bulmaksa, Horner şeması, örnek 3'te tartışıldığı gibi, tüm kökleri tüketene kadar art arda birkaç kez uygulanabilir.

Örnek No.3

Horner şemasını kullanarak $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ polinomunun tüm tamsayı köklerini bulun.

Söz konusu polinomun katsayıları tam sayıdır ve değişkenin en büyük kuvvetinin (yani $x^6$) katsayısı bire eşittir. Bu durumda polinomun tamsayı kökleri serbest terimin bölenleri arasında aranmalıdır. 45 sayısının bölenleri arasındadır. Belirli bir polinom için bu tür kökler 45 $ sayıları olabilir; \; 15; \; 9; \; 5; \; 3; \; 1$ ve -45$; \; -15; \; -9; \; -5; \; -3; \; -1$. Örneğin $1$ sayısını kontrol edelim:

Gördüğünüz gibi, $x=1$ ile $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ polinomunun değeri $192$'a eşittir (son sayı) ikinci satırda) ve $0 $ değil, bu nedenle birlik bu polinomun kökü değildir. Bir tanesinin kontrolü başarısız olduğundan, $x=-1$ değerini kontrol edelim. Bunun için yeni bir tablo oluşturmayacağız ancak tabloyu kullanmaya devam edeceğiz. 1 numara, buna yeni (üçüncü) bir satır ekleniyor. $1$ değerinin kontrol edildiği ikinci satır kırmızı renkle vurgulanacak ve sonraki tartışmalarda kullanılmayacaktır.

Elbette tabloyu yeniden yazabilirsiniz, ancak manuel olarak doldurmak çok zaman alacaktır. Üstelik doğrulaması başarısız olan birden fazla sayı olabilir ve her seferinde yeni bir tablo yazmak zordur. "Kağıt üzerinde" hesaplanırken kırmızı çizgilerin üzeri çizilebilir.

Yani, $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ polinomunun $x=-1$'daki değeri sıfıra eşittir, yani. $-1$ sayısı bu polinomun köküdür. $x^6+2x^5-21x^4-20x^3+71x^2+114x+45$ polinomunu $x-(-1)=x+1$ binomuna böldükten sonra $x polinomunu elde ederiz ^5+x ^4-22x^3+2x^2+69x+45$, katsayıları tablonun üçüncü satırından alınmıştır. 2 (bkz. örnek No. 1). Hesaplamaların sonucu şu şekilde de sunulabilir:

\begin(denklem)x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)(x^5+x^4-22x^3+2x^2 +69x+45)\end(denklem)

Tamsayı kökleri aramaya devam edelim. Şimdi $x^5+x^4-22x^3+2x^2+69x+45$ polinomunun köklerini aramamız gerekiyor. Yine bu polinomun tamsayı kökleri serbest terimi olan $45$ sayısının bölenleri arasında aranır. $-1$ sayısını tekrar kontrol etmeye çalışalım. Yeni bir tablo oluşturmayacağız ancak önceki tabloyu kullanmaya devam edeceğiz. 2 numara, yani Buna bir satır daha ekleyelim:

Yani, $-1$ sayısı $x^5+x^4-22x^3+2x^2+69x+45$ polinomunun köküdür. Bu sonuç şu şekilde yazılabilir:

\begin(denklem)x^5+x^4-22x^3+2x^2+69x+45=(x+1)(x^4-22x^2+24x+45) \end(denklem)

Eşitlik (2) dikkate alınarak eşitlik (1) aşağıdaki biçimde yeniden yazılabilir:

\begin(denklem)\begin(hizalanmış) & x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)(x^5+x^4-22x ^2+2x^2+69x+45)=\\ & =(x+1)(x+1)(x^4-22x^2+24x+45)=(x+1)^2(x^ 4-22x^2+24x+45)\end(hizalanmış)\end(denklem)

Şimdi $x^4-22x^2+24x+45$ polinomunun köklerini - doğal olarak serbest teriminin bölenleri arasında ($45$ sayıları) aramamız gerekiyor. $-1$ sayısını tekrar kontrol edelim:

$-1$ sayısı, $x^4-22x^2+24x+45$ polinomunun köküdür. Bu sonuç şu şekilde yazılabilir:

\begin(denklem)x^4-22x^2+24x+45=(x+1)(x^3-x^2-21x+45) \end(denklem)

Eşitlik (4)'ü hesaba katarak eşitliği (3) aşağıdaki biçimde yeniden yazıyoruz:

\begin(denklem)\begin(hizalanmış) & x^6+2x^5-21x^4-20x^3+71x^2+114x+45=(x+1)^2(x^4-22x^3 +24x+45)= \\ & =(x+1)^2(x+1)(x^3-x^2-21x+45)=(x+1)^3(x^3-x^ 2-21x+45)\end(hizalanmış)\end(denklem)

Şimdi $x^3-x^2-21x+45$ polinomunun köklerini arıyoruz. $-1$ sayısını tekrar kontrol edelim:

Denetim başarısızlıkla sonuçlandı. Altıncı satırı kırmızıyla vurgulayalım ve başka bir sayıyı, örneğin $3$ sayısını kontrol etmeye çalışalım:

Geri kalan sıfırdır, dolayısıyla $3$ sayısı söz konusu polinomun köküdür. Yani $x^3-x^2-21x+45=(x-3)(x^2+2x-15)$. Şimdi eşitlik (5) aşağıdaki gibi yeniden yazılabilir.

Bir polinomun bir noktadaki değerinin hesaplanması en basit klasik programlama problemlerinden biridir.
Çeşitli hesaplama türlerini gerçekleştirirken, argümanların belirli değerleri için polinomların değerlerini belirlemek genellikle gereklidir. Çoğu zaman fonksiyonların yaklaşık hesaplaması, yaklaşık polinomların hesaplanmasına indirgenir.
Habrahabr'ın ortalama okuyucusunun her türlü sapkınlığın kullanımında deneyimsiz olduğu söylenemez. Her iki kişiden biri polinomun Horner kuralı kullanılarak hesaplanması gerektiğini söyleyecektir. Ancak her zaman küçük bir "ama" vardır; Horner'ın planı her zaman en etkilisi midir?

Horner şeması

İstisnalar

Horner'ın planı en ekonomik olduğuna göre başka bir şey var mı?

Bazı durumlarda polinom değerlerini elde etmek için iki aşamalı şemaların kullanılması tavsiye edilir. İlk aşamada sadece polinomun katsayıları üzerinde işlemler yapılır; özel bir forma dönüştürülür. İkinci aşamada, argümanın verilen değerleri için polinomun değeri hesaplanır. Bu durumda ikinci aşamada gerçekleştirilen işlem sayısının Horner şeması kullanılarak yapılan hesaplamalara göre daha az olacağı ortaya çıkabilir.

Yine, bu tür hesaplama yöntemlerinin, çok sayıda x değeri için bir polinomun değerlerini hesaplarken yararlı olduğunu unutmayın. Polinomun ilk aşamasının yalnızca bir kez gerçekleştirilmesi nedeniyle kazanç elde edilir. Bir örnek, yaklaşık polinomun önceden hazırlandığı temel fonksiyonların hesaplanmasıdır.

Daha sonraki tartışmalarda, hesaplama işlemlerinin sayısından bahsederken, hesaplamaların ikinci aşamasının karmaşıklığını aklımda tutacağım.

J. Todt'un 6. derece polinomlar şeması

Katsayılar, koşula bağlı olarak belirlenemeyen katsayılar yöntemiyle belirlenir. Son koşuldan, eşit dereceli polinomların katsayılarını eşitleyen bir denklem sistemi oluşturuyoruz.

Burada sistemin kendisini tanıtmayacağım. Ancak ikinci dereceden denklemlerin çözülmesini gerektiren ikame yöntemi kullanılarak kolayca çözülebilir. Katsayılar karmaşık görünebilir, ancak katsayıların gerçek olduğu ortaya çıkarsa, hesaplamalar Horner'ın şemasına göre beş çarpma ve altı toplama yerine üç çarpma ve yedi toplama gerektirir.

Bu planın evrenselliğinden bahsetmeye gerek yok ama okuyucu Horner'ın planına göre operasyon sayısındaki azalmayı açıkça takdir edebilir.

Şema Yu.L. Ketkova

Yu.L. Ketkov, n>5 için n'inci derece polinomun genel bir temsilini verdi; bu her zaman gerçek ifadelere yol açar ve n'inci derece polinomu hesaplamak için [(n+1)/2]+ çarpma ve n+1 toplama gerektirir.

Örneğin, n=2k ile Ketkov'un şeması polinomları bulmaya indirgenir:

Bilinmeyen katsayıların tümü eşitlikten bulunur. Ketkov'un çalışmalarında, ortaya çıkan sistemlerin çözümü için her zaman gerçek katsayılar veren bir yöntem verilmektedir.

V.Ya'nın şemaları. Pana

V.Ya. Pan, polinomların optimal hesaplanmasına ilişkin problemler üzerinde çalıştı. Özellikle, gerçek polinomların hesaplanması için E. Belaga'nın tahminlerine çok yakın olan çeşitli şemalar önerdi. Gerçek polinomlar için Pan'ın bazı şemalarını vereceğim.
1. Dördüncü dereceden polinomları hesaplama şeması.
Bir polinom dikkate alınır.

Şeklinde sunalım:

Bir polinomun değerini hesaplamak için aşağıdaki ifadeleri kullanırız:

Bu devre ikinci aşamada çarpma ve toplama gerektirir.

Bu şemanın özelliği, orijinal polinom için katsayıların ve gerçek katsayıların her zaman mevcut olmasıdır.

V.Ya'da. Karmaşık olanlar da dahil olmak üzere polinomları hesaplamak için başka şemalar da vardır.

Çözüm

Bununla birlikte, hesaplanması gereken polinom değerlerinin sayısı büyükse ve performans çok önemliyse, o zaman polinomların hesaplanması için özel yöntemlerin kullanılmasının dikkate alınması mantıklı olacaktır.

Bazı okuyucular Horner'ınki dışındaki planlarla uğraşmanın zor, sıkıcı ve uğraşmaya değmeyeceğini söyleyecektir. Bununla birlikte, gerçek hayatta, büyük güçlere sahip çok sayıda polinomun değerini hesaplamanız gereken (örneğin, hesaplamaları aylar sürebilir) ve çarpma sayısını yarı yarıya azaltmak önemli bir sonuç verecektir. Polinomları hesaplamak için belirli bir şema uygulamak için birkaç gün harcamanız gerekse bile zaman kazanırsınız.

Edebiyat

1. Ketkov Yu.L. Polinomları matematiksel makinelerde hesaplamanın yaklaşık bir yolu. // Üniversite Haberleri, cilt 1., Sayı 4, 1958.
2. V. Ya.Pan, “Katsayıların ön işlenmesine sahip şemalar ve parametrelerin otomatik olarak bulunması için bir program kullanılarak polinomların hesaplanması”, Zh. matematik. ve matematik. Fiz., 2:1 (1962), 133–140
3. V. Ya.Pan, “Polinomların değerlerini hesaplama yöntemleri üzerine”, Uspekhi Mat.
4. V. Ya.Pan, “Beşinci ve yedinci derece polinomların gerçek katsayılarla hesaplanması üzerine”, Zh. matematik. ve matematik. Fiz., 5:1 (1965), 116–118
5. Pan V. Ya. Polinomların değerlerini gerçek katsayılarla hesaplamak için bazı şemalar. Sibernetiğin sorunları. Cilt 5.M.: Nauka, 1961, 17–29.
6. Belaga E. G. Katsayıların ön işlenmesi ile bir değişkendeki bir polinomun değerlerinin hesaplanması üzerine. Sibernetiğin sorunları. Cilt 5.M.: Fizmatgiz, 1961, 7–15.

Sitenin geliştirilmesi için yardım edebilir ve bazı fonları aktarabilirsiniz.

Bir polinomun bir noktadaki değerinin hesaplanması en basit klasik programlama problemlerinden biridir.
Çeşitli hesaplama türlerini gerçekleştirirken, argümanların belirli değerleri için polinomların değerlerini belirlemek genellikle gereklidir. Çoğu zaman fonksiyonların yaklaşık hesaplaması, yaklaşık polinomların hesaplanmasına indirgenir.
Habrahabr'ın ortalama okuyucusunun her türlü sapkınlığın kullanımında deneyimsiz olduğu söylenemez. Her iki kişiden biri polinomun Horner kuralı kullanılarak hesaplanması gerektiğini söyleyecektir. Ancak her zaman küçük bir "ama" vardır; Horner'ın planı her zaman en etkilisi midir?


Amacım polinomların hesaplanmasına yönelik algoritmaları doğru bir şekilde tanımlamak değil, yalnızca bazı durumlarda Horner kuralları dışında şemaların uygulanmasının mümkün (gerekli) olduğunu göstermektir. Materyalle ilgilenenler için makalenin sonunda konunun daha detaylı incelenmesi için başvurulabilecek bir referans listesi bulunmaktadır.
Ayrıca bazen Rus matematikçilerimizin isimlerinin az bilinmesi utanç verici hale geliyor. Ayrıca matematikçilerimizin çalışmalarından bahsetmekten de mutluluk duyuyorum.

Horner şeması

İstisnalar

Horner'ın planı en ekonomik olduğuna göre başka bir şey var mı?

Bazı durumlarda polinom değerlerini elde etmek için iki aşamalı şemaların kullanılması tavsiye edilir. İlk aşamada sadece polinomun katsayıları üzerinde işlemler yapılır; özel bir forma dönüştürülür. İkinci aşamada, argümanın verilen değerleri için polinomun değeri hesaplanır. Bu durumda ikinci aşamada gerçekleştirilen işlem sayısının Horner şeması kullanılarak yapılan hesaplamalara göre daha az olacağı ortaya çıkabilir.

Yine, bu tür hesaplama yöntemlerinin, çok sayıda x değeri için bir polinomun değerlerini hesaplarken yararlı olduğunu unutmayın. Polinomun ilk aşamasının yalnızca bir kez gerçekleştirilmesi nedeniyle kazanç elde edilir. Bir örnek, yaklaşık polinomun önceden hazırlandığı temel fonksiyonların hesaplanmasıdır.

Daha sonraki tartışmalarda, hesaplama işlemlerinin sayısından bahsederken, hesaplamaların ikinci aşamasının karmaşıklığını aklımda tutacağım.

J. Todt'un 6. derece polinomlar şeması

Katsayılar, koşula bağlı olarak belirlenemeyen katsayılar yöntemiyle belirlenir. Son koşuldan, eşit dereceli polinomların katsayılarını eşitleyen bir denklem sistemi oluşturuyoruz.

Burada sistemin kendisini tanıtmayacağım. Ancak ikinci dereceden denklemlerin çözülmesini gerektiren ikame yöntemi kullanılarak kolayca çözülebilir. Katsayılar karmaşık görünebilir, ancak katsayıların gerçek olduğu ortaya çıkarsa, hesaplamalar Horner'ın şemasına göre beş çarpma ve altı toplama yerine üç çarpma ve yedi toplama gerektirir.

Bu planın evrenselliğinden bahsetmeye gerek yok ama okuyucu Horner'ın planına göre operasyon sayısındaki azalmayı açıkça takdir edebilir.

Şema Yu.L. Ketkova

Yu.L. Ketkov, n>5 için n'inci derece polinomun genel bir temsilini verdi; bu her zaman gerçek ifadelere yol açar ve n'inci derece polinomu hesaplamak için [(n+1)/2]+ çarpma ve n+1 toplama gerektirir.

Örneğin, n=2k ile Ketkov'un şeması polinomları bulmaya indirgenir:

Bilinmeyen katsayıların tümü eşitlikten bulunur. Ketkov'un çalışmalarında, ortaya çıkan sistemlerin çözümü için her zaman gerçek katsayılar veren bir yöntem verilmektedir.

V.Ya'nın şemaları. Pana

V.Ya. Pan, polinomların optimal hesaplanmasına ilişkin problemler üzerinde çalıştı. Özellikle, gerçek polinomların hesaplanması için E. Belaga'nın tahminlerine çok yakın olan çeşitli şemalar önerdi. Gerçek polinomlar için Pan'ın bazı şemalarını vereceğim.
1. Dördüncü dereceden polinomları hesaplama şeması.
Bir polinom dikkate alınır.

Şeklinde sunalım:

Bir polinomun değerini hesaplamak için aşağıdaki ifadeleri kullanırız:

Bu devre ikinci aşamada çarpma ve toplama gerektirir.

Bu şemanın özelliği, orijinal polinom için katsayıların ve gerçek katsayıların her zaman mevcut olmasıdır.

V.Ya'da. Karmaşık olanlar da dahil olmak üzere polinomları hesaplamak için başka şemalar da vardır.

Çözüm

Bununla birlikte, hesaplanması gereken polinom değerlerinin sayısı büyükse ve performans çok önemliyse, o zaman polinomların hesaplanması için özel yöntemlerin kullanılmasının dikkate alınması mantıklı olacaktır.

Bazı okuyucular Horner'ınki dışındaki planlarla uğraşmanın zor, sıkıcı ve uğraşmaya değmeyeceğini söyleyecektir. Bununla birlikte, gerçek hayatta, büyük güçlere sahip çok sayıda polinomun değerini hesaplamanız gereken (örneğin, hesaplamaları aylar sürebilir) ve çarpma sayısını yarı yarıya azaltmak önemli bir sonuç verecektir. Polinomları hesaplamak için belirli bir şema uygulamak için birkaç gün harcamanız gerekse bile zaman kazanırsınız.

Edebiyat

1. Ketkov Yu.L. Polinomları matematiksel makinelerde hesaplamanın yaklaşık bir yolu. // Üniversite Haberleri, cilt 1., Sayı 4, 1958.
2. V. Ya.Pan, “Katsayıların ön işlenmesine sahip şemalar ve parametrelerin otomatik olarak bulunması için bir program kullanılarak polinomların hesaplanması”, Zh. matematik. ve matematik. Fiz., 2:1 (1962), 133–140
3. V. Ya.Pan, “Polinomların değerlerini hesaplama yöntemleri üzerine”, Uspekhi Mat.
4. V. Ya.Pan, “Beşinci ve yedinci derece polinomların gerçek katsayılarla hesaplanması üzerine”, Zh. matematik. ve matematik. Fiz., 5:1 (1965), 116–118
5. Pan V. Ya. Polinomların değerlerini gerçek katsayılarla hesaplamak için bazı şemalar. Sibernetiğin sorunları. Cilt 5.M.: Nauka, 1961, 17–29.
6. Belaga E. G. Katsayıların ön işlenmesi ile bir değişkendeki bir polinomun değerlerinin hesaplanması üzerine. Sibernetiğin sorunları. Cilt 5.M.: Fizmatgiz, 1961, 7–15.