Модифікований алгоритм Валле-Пуссена

Описано алгоритм одноточкової заміни наближення до точок альтернансу у разі знаходження найкращої рівномірної апроксимації з інтерполюванням. Він полягає в отриманні такого уточнення наближення до точок альтернансу, при якому знаки похибки в точках альтернансу, сусідніх з точкою інтерполювання, спів...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2005
Автор: Малачівський, П.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України 2005
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/20918
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Модифікований алгоритм Валле-Пуссена / П. Малачівський // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 159-166. — Бібліогр.: 9 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-20918
record_format dspace
spelling irk-123456789-209182011-07-29T21:36:18Z Модифікований алгоритм Валле-Пуссена Малачівський, П. Описано алгоритм одноточкової заміни наближення до точок альтернансу у разі знаходження найкращої рівномірної апроксимації з інтерполюванням. Він полягає в отриманні такого уточнення наближення до точок альтернансу, при якому знаки похибки в точках альтернансу, сусідніх з точкою інтерполювання, співпадають. Цей алгоритм ґрунтується на ідеї алгоритму Валле-Пуссена — збереженні порядку зміни знаку похибки апроксимації в новому наближенні до точок альтернансу. Наведено приклад функціонування запропонованого алгоритму. The one-for-one exchange algorithm for alternance points in case of the best uniform (Chebyshev) approximation with interpolation is described. It consists in obtaining so approaching to alternance points, in which the error signs at alternance points, that neighbouring with interpolating point, are the same. As it is known, the error signs are alternative in traditional Vallee-Poussin algorithm. There is given an example of proposed algorithm application. Описан алгоритм одноточечной замены приближения к точкам альтернанса в случае нахождения наилучшей равномерной аппроксимации с интерполированием. Он заключается в получении такого уточнения приближения к точкам альтернанса, при котором знаки погрешностей в точках альтернанса, соседних с точкой интерполирования, совпадают. Этот алгоритм основывается на идее алгоритма Валле-Пуссена — сохранения порядка изменения знака погрешностей аппроксимации в новом приближении к точкам альтернанса. Приведен пример функционирования предложенного алгоритма. 2005 Article Модифікований алгоритм Валле-Пуссена / П. Малачівський // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 159-166. — Бібліогр.: 9 назв. — укр. 1816-1545 http://dspace.nbuv.gov.ua/handle/123456789/20918 518.5 uk Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
description Описано алгоритм одноточкової заміни наближення до точок альтернансу у разі знаходження найкращої рівномірної апроксимації з інтерполюванням. Він полягає в отриманні такого уточнення наближення до точок альтернансу, при якому знаки похибки в точках альтернансу, сусідніх з точкою інтерполювання, співпадають. Цей алгоритм ґрунтується на ідеї алгоритму Валле-Пуссена — збереженні порядку зміни знаку похибки апроксимації в новому наближенні до точок альтернансу. Наведено приклад функціонування запропонованого алгоритму.
format Article
author Малачівський, П.
spellingShingle Малачівський, П.
Модифікований алгоритм Валле-Пуссена
author_facet Малачівський, П.
author_sort Малачівський, П.
title Модифікований алгоритм Валле-Пуссена
title_short Модифікований алгоритм Валле-Пуссена
title_full Модифікований алгоритм Валле-Пуссена
title_fullStr Модифікований алгоритм Валле-Пуссена
title_full_unstemmed Модифікований алгоритм Валле-Пуссена
title_sort модифікований алгоритм валле-пуссена
publisher Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
publishDate 2005
url http://dspace.nbuv.gov.ua/handle/123456789/20918
citation_txt Модифікований алгоритм Валле-Пуссена / П. Малачівський // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 159-166. — Бібліогр.: 9 назв. — укр.
work_keys_str_mv AT malačívsʹkijp modifíkovanijalgoritmvallepussena
first_indexed 2025-07-02T21:28:30Z
last_indexed 2025-07-02T21:28:30Z
_version_ 1836572172457345024
fulltext Модифікований алгоритм Валле-Пуссена Петро Малачівський к. т. н., с. н. с., Центр математичного моделювання ІППММ НАН України, вул. Дж. Дудаєва, 15, Львів, 79005, e-mail: psmal@cmm.lviv.ua Описано алгоритм одноточкової заміни наближення до точок альтернансу у разі знаходже- ння найкращої рівномірної апроксимації з інтерполюванням. Він полягає в отриманні такого уточнення наближення до точок альтернансу, при якому знаки похибки в точках альтер- нансу, сусідніх з точкою інтерполювання, співпадають. Цей алгоритм ґрунтується на ідеї алгоритму Валле-Пуссена — збереженні порядку зміни знаку похибки апроксимації в новому наближенні до точок альтернансу. Наведено приклад функціонування запропонованого алгоритму. Ключові слова: чебишовське (рівномірне) наближення, точки чебишовсь- кого альтернансу, схема Ремеза, алгоритм Валле-Пуссена. Вступ. Алгоритм Валле-Пуссена [1] визначає спосіб отримання наступного на- ближення до точок чебишовського альтернансу зі збереженням черговості зміни знаку похибки в сусідніх точках альтернансу. Проте в деяких задачах найкращого рівномірного наближення знак похибки в сусідніх точках альтернансу не завжди чергується [2-5]. Зокрема, у випадку рівномірного наближення з інтерполюванням знаки похибки в точках альтернанту, сусідніх з точкою інтерполювання, співпа- дають [4, 6-8]. Тому для заміни точок альтернансу в цих випадках алгоритм Вал- ле-Пуссена не годиться, оскільки він передбачає чергування зміни знаку похибки. Деякі часткові алгоритми заміни наближення до точок альтернанcу, у разі співпа- дання знаків похибки апроксимації в точках альтернансу, сусідніх з точкою інтер- полювання, розглянуто в роботах [7, 9]. У цих роботах описано схеми отримання нового наближення до точок альтернансу лише для невеликої їх кількості, а саме — двох і трьох точок альтернансу. 1. Опис алгоритму заміни наближення до точок альтернансу у випадку рівномірної апроксимації з інтерполюванням Розглянемо можливий варіант заміни наближення до точок альтернансу для рів- номірної апроксимації з інтерполюванням, дотримуючись ідеї алгоритму Валле- Пуссена. Алгоритм Валле-Пуссена — це алгоритм одноточкової заміни набли- ження до точок альтернансу. Його суть полягає в тому, що нова точка, а саме точка, в якій досягається найбільша за абсолютною величиною похибка апрокси- УДК 518.5 159 Петро Малачівський Модифікований алгоритм Валле-Пуссена 160 мації, вводиться в альтернанс так, щоб не порушити порядку зміни знаку похибки в новому наближенні до точок альтернансу відповідно до характеристичної властивості. Важливим моментом алгоритму заміни наближення до точок аль- тернансу, у випадку рівномірного наближення з однією точкою інтерполювання u, є дотримання умови співпадання похибки апроксимації в точках альтернанту, сусідніх з точкою u. Нехай після j-ої ітерації за схемою Ремеза на множині точок альтернансу )( j iz , 1,1 += mi з’ясувалося, що максимальна за модулем похибка апроксимації jρ більша від похибки в точках альтернансу jµ ( )jj µ>ρ і вона досягається в деякій точці xr ( ) ( )xx jxxxrjj N ρ=ρ≡ρ ≤≤1 max , (1) де ( )xjρ — похибка апроксимації функції f(x) виразом ( )( )xaF j m ; з ваговою функцією ( )xw ( ) ( ) ( )( ) ( )xw xaFxfx j m j ;− =ρ , ( )ja — параметри апроксимації, що відповідають j -ій ітерації за схемою Реме- за. Нехай взаємне розташування точки u щодо j -го наближення до точок аль- тернансу буде таким ( ) ( ) ( ) ( ) ( )j m j k j k jj zzuzzz 1121 ...... ++ <<<<<<< . (2) Якщо точка xr, у якій досягається максимальна за модулем похибка апроксимації, розташована лівіше k -ої точки альтернансу ( )j kr zx < , або правіше ( )1+k -ої — ( )j kr zx 1+> , то заміна наближення до точок альтернансу проводиться за алгоритмом Валле-Пусенна. Особливість уточнення наближення до точок альтернансу стосу- ється лише випадку, коли точка xr знаходиться поруч із точкою інтерполювання u , тобто коли вона розташована поміж точками альтернансу ( )j kz і ( )j kz 1+ ( ) ( )j kr j k zxz 1+<< . (3) У цьому випадку можливі два варіанти розташування точки rx щодо точки u 1) uxz r j k <<)( — точка rx розташована зліва точки u ; 2) )( 1 j kr zxu +>> — точка rx розташована справа від точки u . Розглянемо отримання (j+1)-го наближення до точок альтернансу для кож- ного з цих випадків. У першому випадку, коли точка rx розташована зліва від точки u , її введення в наближення до точок альтернансу проводимо таким ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2005, вип. 2, 159-166 161 чином. Якщо знак похибки апроксимації в точці rx співпадає зі знаком похибки в точці альтернансу )( j kz ( )( ) ( )( )( )j kjrj zx ρ=ρ signsign , (4) то в новому наближенні до точок альтернансу замінюємо точку )( j kz ( ) r j k xz =+1 , (5) а у протилежному разі замінюємо точку )( 1 j kz + r j k xz =+ + )1( 1 . (6) Решта точок альтернансу залишається без зміни. Такий порядок отримання ново- го наближення до точок альтернансу забезпечує дотримання умов співпадання знаку похибки апроксимації в точках альтернансу, сусідніх із точкою u. Розглянутий випадок уточнення наближення до точок альтернансу на ( )1+j -ій ітерації графічно ілюструють рисунки 1 і 2. Криві, зображені на цих рисунках, є графіками похибки апроксимації деякої функції ( )xf виразом від п’яти параметрів ( )( )xaF j ;5 . Точка rx , в якій досягається найбільше за модулем значення похибки апроксимації, розташована поміж точкою альтернансу ( )jz3 і точкою u . Оскільки знак похибки апроксимації в точці rx співпадає зі знаком похибки в точці альтернансу ( )jz3 (див. рис. 1), то точка rx вводиться в наступне наближення до точок альтернансу замість ( )jz3 . На цьому рисунку і на наступних зірочкою відзначено точку альтернансу, замість якої вводиться точка rx . Рис. 1. Заміна точок альтернансу у разі виконання умови (4) Петро Малачівський Модифікований алгоритм Валле-Пуссена 162 На рис. 2 зображено порядок заміни наближення до точок альтернансу у випадку невиконання умови (3). У цьому разі точка rx вводиться в наступне на- ближення до точок альтернансу замість точки ( )jz4 . У новому наближенні до то- чок альтернансу точка u буде розташована вже поміж четвертою й п’ятою точ- ками альтернансу ( ) ( )1 5 1 4 ++ << jj zuz , в яких знаки похибки апроксимації збігаються. У другому випадку, коли точка rx , у котрій досягається найбільша похиб- ка апроксимації, розташована справа від точки u ( ))( 1 j kr zxu +>> , нове набли- ження до точок альтернансу отримується в такий спосіб. Якщо знак похибки апроксимації в точці rx співпадає зі знаком похибки в точці альтернансу )( 1 j kz + ( )( ) ( )( )( )j kjrj zx 1signsign +ρ=ρ , (7) то в новому наближенні цю точку замінюємо r j k xz =+ + )1( 1 , (8) а решту точок альтернансу залишаємо без зміни. Якщо ж умова (7) не виконується, то ( )1+j -е наближення до точок альтер- нансу отримується з j -го, в якому точка )( j kz замінюється на точку rx r j k xz =+ )1( . (9) Зазначимо, що в цьому разі сусідніми точками альтернансу до точки u будуть точки )1( 1 + − j kz і )1( +j kz . В отриманому таким чином ( )1+j -му наближенні до точок альтернансу також забезпечується дотримання умови співпадання знаків похиб- ки апроксимації в точках альтернансу, сусідніх із точкою u . Рис. 3 і 4 ілюстру- ють можливі варіанти вибору чергового наближення до точок альтернансу у випадку, коли точка rx , з найбільшою похибкою апроксимації, розташована Рис. 2. Заміна точок альтернансу у разі невиконання умови (4) ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2005, вип. 2, 159-166 163 справа від точки u . Оскільки знак похибки апроксимації в точці xr співпадає зі знаком похибки в точці альтернанансу )( 4 jz (див. рис. 3), то точка rx вводиться в наступне наближення до точок альтернансу замість )( 4 jz . На рис. 4 показано порядок заміни наближення до точок альтернансу у разі неспівпадання знаку похибки апроксимації в точці rx і точці альтернансу )( 4 jz , тобто невиконання умови (7). У цьому випадку точка rx вводиться в наближення до точок альтернансу замість точки )( 3 jz . Таким чином, у модифікованому алгоритмі Валле-Пуссена наступне на- ближення до точок альтернансу, як і в алгоритмі Валле-Пуссена, відрізняється від попереднього тим, що замість однієї із його точок розглядаємо точку rx , в якій досягається найбільша за модулем похибка апроксимації. При цьому задо- вольняється умова дотримання порядку зміни знаку похибки апроксимації відповідно до характеристичної (альтернансної) властивості. Введення в нове наближення до точок альтернасу точки rx , в якій досяга- ється найбільша похибка апроксимації, з дотриманням порядку зміни знаку по- хибки апроксимації в точках альтернансу, призводить до збільшення похибки Рис. 4. Заміна точок альтернансу в разі невиконання умови (7) Рис. 3. Заміна точок альтернансу в разі виконання умови (7) Петро Малачівський Модифікований алгоритм Валле-Пуссена 164 апроксимації 1+µ j у точках альтернансу на черговій ( )1+j -ій ітерації схеми Ремеза. Згідно ідеї Є. Я. Ремеза [1], це водночас зумовлює зменшення значення по- хибки апроксимації 1+ρ j . Саме цей факт використовується для доведення збіж- ності алгоритму Ремеза [1, 7]. Зазначимо, що в монографіях [7, 8] обґрунтовано, що у разі виконання умов існування найкращого рівномірного наближення з інтерполюванням, метод Ремеза збігається за скінченну кількість кроків, незалежно від початкового на- ближення до точок альтернансу, а саме під час апроксимації виразом з m пара- метрами він збігається щонайбільше за ( )2+m -і ітерації. А тому, із застосуван- ням модифікованого алгоритму Валле-Пуссена для заміни точок альтернансу, він також збігатиметься не більше, ніж за ( )2+m -і ітерації. У разі рівномірної апроксимації з інтерполюванням у декількох точках, особливості заміни наближення до точок альтернансу стосуються лише тих випадків, коли точка, в якій досягається найбільша похибка апроксимації, зна- ходиться поруч котроїсь із точок інтерполювання. Тоді, залежно від співвідно- шення між знаками похибок апроксимації в точці, в якій спостерігається най- більше за модулем значення похибки, і сусідній з нею точці альтернансу, уточ- нення наближення до точок альтернансу, проводиться відповідно до опису (5-9). 2. Приклад функціонування модифікованого алгоритму Валле-Пуссена Функціонування модифікованого алгоритму Валле-Пуссена розглянемо на прик- ладі апроксимації поліномом третього степеня функції, яка задана значеннями в 13 точках (див. колонки х і ( )xf у таблиці) на відрізку [ ]8,1;3− із найменшою абсолютною похибкою і точним відтворенням значення в точці 6,0=x . У колонках 1∆ , 2∆ і 3∆ наведено значення похибок апроксимації відпо- відно після першої, другої і третьої ітерації схеми Ремеза. Значення похибки апроксимації у точках альтернансу серед результатів кожної ітерації виділено підкресленням, найбільше значення похибки апроксимації — жирним шрифтом, а точка інтерполювання — курсивом. Як і очікувалось, наведені в таблиці ре- зультати знаходження рівномірної апроксимації з найменшою абсолютною по- хибкою функції ( )xf підтверджують поступове зменшення похибки апроксима- ції до виконання характеристичної властивості: досягнення максимальної похибки апроксимації у точках альтернансу. Графіки похибок апроксимації після кожної ітерації схеми Ремеза зобра- жено на рис. 5. Точка інтерполювання на цьому графіку відзначена кружечком. Такими ж кружечками відзначені й точки альтернансу. Проміжкові точки набли- ження до точок альтернансу, які відмінні від кінцевих, відзначені зірочками. ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2005, вип. 2, 159-166 165 Цифри у дужках поруч із точками альтернансу та наближення до них вказують на номер ітерації. Таблиця Значення похибок апроксимації на ітераціях схеми Ремеза із застосуванням модифікованого алгоритму Валле-Пуссена № з/n x ( )xf 1∆ 2∆ 3∆ 1 -3,00 -106,28223739 0,05838 0,18723 0,19388 2 -2,60 -68,16379261 -0,13444 -0,16007 -0,16139 3 -2,20 -39,11139393 -0,05838 -0,18723 -0,19388 4 -1,80 -17,95729155 0,12603 -0,06171 -0,07140 5 -1,40 -3,57409732 0,29860 0,08931 0,07851 6 -1,00 5,11705941 0,38766 0,18723 0,17689 7 -0,60 9,14591688 0,37066 0,20255 0,19388 8 -0,20 9,50026281 0,26703 0,14773 0,14158 9 0,20 7,13973959 0,12432 0,06338 0,06023 10 0,60 3,01408459 -0,00000 -0,00000 -0,00000 11 1,00 -1,91705674 -0,05838 -0,00180 0,00112 12 1,40 -6,66590037 -0,03141 0,07044 0,07570 13 1,80 -10,20270491 0,05838 0,18723 0,19388 Висновки. Розвиваючи ідею алгоритму Валле-Пуссена, запропоновано спосіб отримання нового наближення до точок альтернансу, із дотриманням порядку зміни знаку похибки апроксимації відповідно до характеристичної властивості Рис. 5. Графіки похибок апроксимації на окремих ітераціях схеми Ремеза Петро Малачівський Модифікований алгоритм Валле-Пуссена 166 рівномірної апроксимації з інтерполюванням. Власне модифікація алгоритму Валле-Пуссена стосується лише випадку, коли точка з найбільшою за модулем похибкою апроксимації розташована поруч із точкою інтерполювання. Залежно від знаків похибок апроксимації в точці з найбільшою за модулем похибкою і сусідній з нею точці альтернансу запропоновано чотири варіанти проведення заміни наближення до точок альтернансу (5)-(9). При цьому, як і в разі застосу- вання алгоритму Валле-Пуссена, під час чергових ітерацій схеми Ремеза значен- ня похибки апроксимації в точках альтернансу щоразу збільшується, а значення максимальної за модулем похибки апроксимації — зменшується. За такого уточ- нення наближення до точок альтернансу схема Ремеза збігається. Література [1] Ремез Е. Я. Основы численных методов чебышевского приближения. — К.: Наук. думка, 1969. — 623 с. [2] Fike C. T. Computer evaluation of mathematical function // New Jersey: Prentice-Hall, 1968. — 228 p. [3] Демьянов В. Ф., Малоземов В. Н. Введение в минимакс. — М.: Наука, 1972. — 368 с. [4] Коллатс Л., Альберт Ю. Задачи по прикладной математике. — М.: Мир, 1978. — 168 с. [5] Коллатс Л., Крабе В. Теория приближений. Чебышевские приближения и их прило- жения: Пер. с нем. — М.: Наука, 1978. — 272 с. [6] DeVore R., Yan Z. Error analysis for piecewise curve fitting algorithms, Computer Aided Geometric Design 3, 1986. — P. 205-215. [7] Попов Б. А., Теслер Г. С. Приближение функций для технических приложений. — К.: Наук. думка, 1980. — 352 с. [8] Попов Б. А. Pавномерное приближение сплайнами. — К.: Наук. думка, 1989. — 272 с. [9] Мельничук Л. С., Попов Б. А. Наилучшее приближение табличных функций с усло- вием // В книге: Алгоритмы и программы для вычисления функций на ЭЦВМ. — К.: Ин-т кибернетики, 1977. — Вып.4. — С. 189–200. Modified Vallee-Poussin Algorithm Petro Malachivskyj The one-for-one exchange algorithm for alternance points in case of the best uniform (Chebyshev) approximation with interpolation is described. It consists in obtaining so approaching to alternance points, in which the error signs at alternance points, that neighbouring with interpolating point, are the same. As it is known, the error signs are alternative in traditional Vallee-Poussin algorithm. There is given an example of proposed algorithm application. Модифицированный алгоритм Валле-Пуссена Петро Малачивский Описан алгоритм одноточечной замены приближения к точкам альтернанса в случае на- хождения наилучшей равномерной аппроксимации с интерполированием. Он заключается в получении такого уточнения приближения к точкам альтернанса, при котором знаки по- грешностей в точках альтернанса, соседних с точкой интерполирования, совпадают. Этот алгоритм основывается на идее алгоритма Валле-Пуссена — сохранения порядка измене- ния знака погрешностей аппроксимации в новом приближении к точкам альтернанса. Приведен пример функционирования предложенного алгоритма. Отримано 25.09.05