Текст подпрограммы и версий
ia83r.zip , ia83d.zip
Тексты тестовых примеров
tia83r.zip , tia83d.zip
Текст подпрограммы и версий ( Си )
ia83r_c.zip , ia83d_c.zip
Тексты тестовых примеров ( Си )
tia83r_c.zip , tia83d_c.zip
Текст подпрограммы и версий ( Паскаль )
ia83r_p.zip , ia83e_p.zip
Тексты тестовых примеров ( Паскаль )
tia83r_p.zip , tia83e_p.zip

Подпрограмма:  IA83R

Назначение

Построение алгебраического полинома наилучшего равномерного приближения для таблично заданной функции.

Математическое описание

Пусть в узлах сетки  x1 < x2 < ...< xM заданы значения табличной функции  y :  y1, y2 ..., yM. Требуется построить алгебраический полином

                         N
         P*(x)  =   ∑   ak xk
                       k =0 

заданной степени N ≤ M - 2, который минимизирует максимальное отклонение

                 h ( y,P )   =    max   | yk - P(x) |   
                                     1≤k≤M 

среди всех полиномов P (x) степени N.

Среди узлов  x1, x2, ..., xM существуют точки альтернанса  x1* < x2* < ... < x*N + 2, в которых

                 yk - P* (xk*)  =  (- 1)k h* , 

 где  h*  =   max    | yk - P*(xk ) | , 
                 1≤k≤M 

h* - максимальное отклонение полинома наилучшего приближения P* (x).

Задача решается на основе итерационного R - алгоритма В.Н.Малоземова, требующего задания начального набора N + 2 точек x1 < x2 < ...< xN + 2, каждая из которых должна совпадать с одним из узлов исходной сетки. Подпрограмма находит точки альтернанса  x1* < x2* < ...< x*N + 2, не обязательно совпадающие с начальным набором точек.

Сб. "Вопросы теории и элементы программного обеспечения минимаксных задач", под ред. Демьянова В.Ф., Малоземова В.Н., Л., Изд - во Ленингр. ун - та, 135 - 138, 1977.

Использование

    SUBROUTINE  IA83R (M, N, X, Y, IN, ITER, A, AX, JN, RAB, IERR) 

Параметры

M - заданное число узлов сетки (тип: целый);
N - заданная степень полинома, N ≤ M - 2 (тип: целый);
X - вещественный вектор длины M, в котором задаются значения узлов сетки;
Y - вещественный вектор длины M, в котором задаются значения табличной функции;
IN - целый вектор длины N + 2 номеров начального набора точек; может изменяться самой программой в процессе вычисления;
ITER - число выполненных при решении задачи итераций (тип: целый);
A - вещественный вектор длины N + 1 вычисленных значений коэффициентов полинома наилучшего приближения, A ( I ) = aI,  I = 1, 2, ...,N + 1;
AX - вещественный вектор длины N + 2 вычисленных значений точек альтернанса;
JN - целый вектор длины N + 2 номеров вычисленных значений точек альтернанса;
RAB - вещественный двумерный массив размера 2 * (N + 2), используемый как рабочий; после окончания работы подпрограммы RAB (1, 1) = h*;
IERR - целая переменная, служащая для сообщения об ошибках, обнаруженных в ходе работы подпрограммы; при этом
IERR=65 - когда M < N + 2;
IERR=66 - когда номера начального набора точек не упорядочены строго по возрастанию; или упорядоченность нарушается в процессе работы программы;
IERR=67 - когда значения узлов сетки  xi,  i = 1, 2, ..., M не упорядочены строго по возрастанию.
IERR=68 - сходимость не может быть достигнута в пределах 30 итераций.

Версии

IA83D - построение алгебраического полинома наилучшего равномерного приближения для таблично заданной функции в режиме вычислений с удвоенной точностью.

Вызываемые подпрограммы

UTIA10 - подпрограмма выдачи диагностических сообщений при работе IA83R.
UTIA11 - подпрограмма выдачи диагностических сообщений при работе IA83D.

Замечания по использованию: нет

Пример использования

       DIMENSION  X(51), Y(51), IN(9), A(8), AX(9), JN(9), RAB(2,9)
       DATA  IN /1, 6, 11, 16, 21, 26, 31, 36, 51/
       M = 51
       N = 7
       H = 2./(M - 1)
       DO 5  K = 1, M
       X(K) = - 1. + (K - 1)*H
       Y(K) = ABS(X(K))
    5 CONTINUE
       CALL  IA83R (M, N, X, Y, IN, ITER, A, AX, JN, RAB, IERR)

Результаты:   
      
       IERR = 0;     ITER = 6;
       RAB(1,1) = 0.04587;
 
       A = (0.04587, 0., 2.8698, 0., - 4.18189, 0., 2.31212, 0.);
       AX = (- 1., -.880, -.56, -.2, 0., .2, .56, .88, 1.);

       JN = (1, 4, 12, 21, 26, 31, 40, 48, 51)