Ўзбекистон республикаси олий ва ўрта махсус таълим вазирлиги тошкент кимё – технология институти

Кўпҳад қийматини Горнер схемаси билан ҳисоблаш. Алгоритмлар. Тақрибий ҳисоблашларда итерацион цикллардан фойдаланиш (қаторларни йиғиндисини ҳисоблаш). Алгоритмлар

Кўпҳадлар берилиши. Итерацион ҳисоблаш жараёни.

Кўпҳадларни ҳисоблашни Горнер схемаси.
Горнер схемасини алгоритми ва дастур коди


Кўпҳад қийматини Горнер схемаси билан ҳисоблаш.
n – даражали кўпҳад берилган бўлсин
Р(х) = a₀Xⁿ + a₁X^n-1 + . . . + a_n-1X +a_n (1)
кўпҳаднинг a_к коэффициентлари хақиқий бўлсин (к= 0,1,2, ,,, n). Масала қўйилиши қуйидагдан иборатдир: Х = ξ нуқтада кўпҳад қийматини топиш керак. Яъни :
Р(ξ) = a₀ξ ⁿ + a₁ξ ^n-1 + . . . + a_n-1 ξ +a_n (2)

Р(ξ) сонини топиш жараёнини қуйидагича келтирамиз, (2) – формулани қуйидаги ҳолатга келтирамиз:

Р(ξ) = (,,,(((a₀ξ + a₁)ξ +a₂ ) ξ +a₃) ξ + . . . + a_n-1 )ξ +a_n)

Бу тенгликдан кетма кет ҳисоблаб :

b₀ = a₀
b₁ = a₁ + b₀ ξ
b₂ = a₂ + b₁ ξ
b₃ = a₃ + b₂ ξ (3)
b₄ = a₄ + b₃ ξ
…………….
b_n = a_n + b_n-1 ξ
b_n = Р(ξ) ларни топамиз.
b₀ = a₀ , b₁, …b_n-1 сонлар , Р(х) кўпҳадни х - ξ бир ҳадга бўлиш натижасида ҳосил бўлган бўлинма Q(x) кўпҳаднинг коэффициентлари эканлигини кўрсатамиз. Фараз қиламизки
Q(x) = β₀ x^n-1 + β₁x^n-2 + … + β_n-1 (4)
ва
Р(х) = Q(x)(х- ξ) + β_n (5)
Безу теоремаси асосида бўлиш натижасида хосид бўладиган қолдиқ
β_n = Р(ξ) тенг бўлади. (4) ва (5) – формулалардан қуйидагиларни ҳосил қиламиз:
Р(х) = (β₀ x^n-1 + β₁x^n-2 + … + β_n-1) (x- ξ) + β_n

ёки қавсларни очиб ўхшаш ҳадларни келтириб қуйидаги ҳолатга келтирамиз:

Р(х) = (β₀ xⁿ + (β₁ - β₀ ξ) x ^n-1 +( β₂ - β₁ ξ) x^n-2 + … +( β_n-1 - β_n-2 ξ) x +( β_n - β_n-1 ξ)

тенгликни ўнг ва чап томонларидаги х ўзгарувчини бир хил даражалари олдидаги коэффициентларини солиштириб ҳосил қиламиз:

β₀ = a₀

β₁ - β₀ ξ = a₁
β₂ - β₁ ξ = a₂
....................
β_n-1 - β_n-2 ξ = a_n-1
β_n - β_n-1 ξ = a_n
бундан
β₀ = a₀ = b₀
β₁ = a₁ + β₀ ξ = b₁
β₂ = a₂ + β₁ ξ = b₂
………………….
β_n-1 = a_n-1 + β_n-2 ξ = b_n-1
β_n = a_n + β_n-1 ξ = b_n

шу билан юқорида қабул қилган тахминимиз исботини топди.

Шундай қилиб (3) – формулалар ёрдамида бўлиш амалини бажармасдан,
Q(x) бўлинма коэффициентларини ва қолдиқ Р(ξ) ни топиш мумкин.Ушбу ҳисобларни Горнер схемаси деб аталадиган схема бўйича бажариладилар:
a₀, a₁, a₂, … a_n
+ ∟ ξ
b₀ ξ b₁ ξ … b_n-1 ξ
__________________
b₀ b₁ b₂ … b_n = P(ξ)

Мисол . P(X) = 3x³+ 2x² -5x +7 кўпҳад қийматини х=3 да ҳисобланг:

3 2 -5 7
+ ∟ 3
9 33 84
_____________________
3 11 28 91= P(3)
Горнер схемаси бўйича ҳисоблаш алгоритмини ва Pascal дастурлаш тилида тузилган дастур кодини келтирамиз:
a(0), … , a(n) коэфициентларга эга n – даражали кўпҳад берилган бўлсин. Бу кўпҳадни Горнер схемасига биноан берилган нуқтада ҳисоблаш қуйидагича бажарилади. Кўпҳадни Р десак, унда Р кўпҳад Горнер схемаси бўйича S=(…((а(0)*х+а(1))*х+а(2))*х+…)*х+а(n) кўринишга келтирилиди. Демак ҳисоблаш жараёни P:=a(i) ни керакли маротаба Х га кўпайтиришдан ва a(i) ни қўшишдан иборат бўлади.
Горнер схемаси бўйича кўпҳад қийматини ҳисоблаш учун Pascal дастурлаш тилида тузилган дастур кодини келтирамиз:
Бунда n кўпҳад ўзгарувчиларининг даражаси, a[i] – коэффициентлари.
Program Gor; Const n=10;