Невиллес алгоритмі - Nevilles algorithm - Wikipedia

Математикада, Невиллдің алгоритмі үшін қолданылатын алгоритм болып табылады көпмүшелік интерполяция математик шығарған Эрик Гарольд Невилл[дәйексөз қажет ]. Берілген n + 1 балл, дәреженің ерекше полиномы бар ≤ n берілген нүктелер арқылы өтеді. Невилл алгоритмі осы көпмүшені бағалайды.

Невиллдің алгоритмі Ньютон формасы үшін интерполяциялайтын көпмүшенің және рекурсиялық қатынастың бөлінген айырмашылықтар. Бұл ұқсас Айткеннің алгоритмі (атымен Александр Айткен ), ол қазіргі кезде қолданылмайды.

Алгоритм

Жиынтығы берілген n+1 деректер нүктесі (хмен, жмен) онда екі емес хмен бірдей, интерполяциялайтын көпмүшелік - көпмүшелік б дәрежесі n мүлікпен

б(хмен) = жмен барлығына мен = 0,…,n

Бұл көпмүше бар және ол ерекше. Невилл алгоритмі көпмүшені белгілі бір уақытта бағалайды х.

Келіңіздер бмен,j дәреженің көпмүшесін белгілеңіз jмен ол нүктелер арқылы өтеді (хк, жк) үшін к = мен, мен + 1, …, j. The бмен,j қайталану қатынасын қанағаттандыру

Бұл қайталануды есептеуге боладыб0,n(х), бұл ізделінетін құндылық. Бұл Невиллдің алгоритмі.

Мысалы, үшін n = 4, қайталануды төмендегі үшбұрышты кестені солдан оңға қарай толтыру үшін пайдалануға болады.

Бұл процесс нәтиже береді б0,4(х), арқылы өтетін көпмүшенің мәні n + 1 деректер нүктесі (хмен, жмен) нүктесінде х.

Бұл алгоритм қажет O (n2) өзгермелі нүктелік операциялар.

Көпмүшенің туындысын дәл осылай алуға болады, яғни:

Сандық дифференциацияға қолдану

Лайз және Молер 1966 жылы Невиллдің алгоритміндегі көпмүшеліктер үшін анықталмаған коэффициенттерді қолданып, бастапқы интерполяциялайтын көпмүшенің Маклорин кеңеюін есептей алатынын көрсетті, бұл функцияның туындылары үшін бастапқы жақтауларына сандық жуықтаулар береді. «Бұл процесс арифметикалық амалдарды шекті айырмашылық әдістерінде талап етілгеннен гөрі көбірек қажет етеді» дегенмен, «функцияны бағалау үшін нүктелерді таңдау ешқандай жолмен шектелмейді». Олар сондай-ақ олардың әдісін Вандермонд типіндегі сызықтық жүйелердің шешіміне тікелей қолдануға болатындығын көрсетеді.

Әдебиеттер тізімі

  • Пресс, Уильям; Саул Теукольский; Уильям Веттерлинг; Брайан Фланнери (1992). «§3.1 полиномдық интерполяция және экстраполяция (шифрланған)» (PDF). C.-дегі сандық рецепттер. Ғылыми есептеу өнері (2-ші басылым). Кембридж университетінің баспасы. дои:10.2277/0521431085. ISBN  978-0-521-43108-8. (сілтеме нашар)
  • Линес және К.Б.Молер, Ван Дер Монде жүйелері және сандық дифференциация, Numerische Mathematik 8 (1966) 458-464 (доии: 10.1007 / BF02166671 )
  • Невилл, Э.Х .: Итеративті интерполяция. Дж. Үнді математикасы. Soc.20, 87–120 (1934)

Сыртқы сілтемелер