Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации

Рассматривается проблема наилучшей чебышевской аппроксимации для эффективной обработки инфор- мации. Дается обоснование преимуществ разработанных алгоритмов аппроксимации, которые связаны с их оптимизацией по точности и быстродействию. Розглядається проблема найкращої чебишовської апроксимації для...

Full description

Saved in:

Bibliographic Details
Date:	2009
Main Author:	Каленчук-Порханова, А.А.
Format:	Article
Language:	Russian
Published:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Subjects:	Интеллектуальный анализ данных
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/8018
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации / А.А. Каленчук-Порханова // Штучний інтелект. — 2009. — № 3. — С. 53-63. — Бібліогр.: 13 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859628280199512064
author	Каленчук-Порханова, А.А.
author_facet	Каленчук-Порханова, А.А.
citation_txt	Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации / А.А. Каленчук-Порханова // Штучний інтелект. — 2009. — № 3. — С. 53-63. — Бібліогр.: 13 назв. — рос.
collection	DSpace DC
description	Рассматривается проблема наилучшей чебышевской аппроксимации для эффективной обработки инфор- мации. Дается обоснование преимуществ разработанных алгоритмов аппроксимации, которые связаны с их оптимизацией по точности и быстродействию. Розглядається проблема найкращої чебишовської апроксимації для ефективної обробки інформації. Наводяться обґрунтування переваг алгоритмів апроксимації, що пов’язано з їх оптимізацією за точністю та швидкодією. The problem of the best Chebyshev’s approximation for effective treatment of information is considered. The advantages of the algorithms elaborated which are connected with their accuracy and performance optimization are presented.
first_indexed	2025-11-29T14:15:16Z
format	Article
fulltext	«Штучний інтелект» 3’2009 53 2К УДК 519.651.2 А.А. Каленчук-Порханова Институт кибернетики им. В.М. Глушкова НАН Украины, г. Киев ioanna@public.icyb.kiev.ua Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации Рассматривается проблема наилучшей чебышевской аппроксимации для эффективной обработки инфор- мации. Дается обоснование преимуществ разработанных алгоритмов аппроксимации, которые связаны с их оптимизацией по точности и быстродействию. Введение Решение проблемы информатизационного обеспечения общества является всё бо- лее актуальным и определяющим условием его эффективного развития. Информация о состояниях исследуемых процессов в природе и обществе как результат проведения измерений является, как правило, дискретным представлением в виде информационных массивов числовых данных о функциональных зависимостях, характеризующих эти про- цессы. Трудности, а зачастую и невозможность использовать массивы возникают при решении таких прикладных задач, как математическое моделирование и прогнози- рование, определение функциональной закономерности природы исследуемого процесса (например, в виде эмпирической формулы), и при решении проблем экономного хране- ния больших по объему массивов данных либо скоростной передаче по каналам связи, а также при возобновлении значений функциональной зависимости на «неосвещённых замерами» участках (обратная задача) и др. Эти трудности преодолеваются путём замены (сжатия) больших массивов аналитическими выражениями с небольшим коли- чеством параметров (прямая задача). Для решения этой проблемы применяются средства аналитической обработки данных на основе методов и алгоритмов аппроксимации (приближения) функций. Пред- лагается эффективный способ аналитической обработки данных, обеспечивающий высокую точность приближения и использующий аппроксимирующие аналитические выражения разных типов [1]. Этот способ основан на методах и алгоритмах чебышёв- ской наилучшей аппроксимации, который имеет существенное преимущество перед интерполяционным и среднеквадратическим способами приближения. Причём главное преимущество этого способа – обеспечение требуемой гарантированной точности приб- лижения во всей непрерывной области задания функции позволяет сохранять получен- ную точность во всех точках при решении обратной задачи. Разработанные автором алгоритмы основаны на методе Е.Я. Ремеза последова- тельных чебышёвских интерполяций (п.ч.и.) [2] и, в свою очередь, обладают преиму- ществами перед алгоритмами других авторов, так как для них проведен анализ всех видов погрешностей с целью их оптимизации по точности и быстродействию [3], [4]. Основные задачи аналитической обработки данных. В зависимости от цели аналитической обработки массивов числовых данных можно выделить такие основные задачи, для решения которых используются методы и алгоритмы аппроксимации функ- Каленчук-Порханова А.А. «Искусственный интеллект» 3’2009 54 2К ций. В то же время следует заметить, что с точки зрения теории аппроксимации эти за- дачи тесно связаны между собой и решение одной из них часто используется для реше- ния других. Задача аналитичного представления массивов числовых данных состоит в прибли- жении дискретно заданной функциональной зависимости f различными типами анали- тических выражений (аппроксимантов) F с целью их эффективного использования при решении различных прикладных проблем. Задача поиска эмпирических закономерностей процесса, выраженного экспери- ментальными данными, с целью построения эмпирических формул состоит в том, что полученная таблица значений измеряемых величин ix и iy ( N,i 1 ) является прибли- женным представлением некоторого эмпирического закона  A;xF , который характе- ризуется небольшим количеством параметров A = {a0, a1,…, an} и для определения которого используется тот или иной способ приближения. Задача сжатия численной информации в виде больших по объему массивов числовых данных состоит в приближенной замене дискретно заданной функции f на одномерной или многомерной сетке некоторым аналитическим выражением F с неболь- шим числом параметров. Эта задача характеризуется коэффициентом сжатия С, кото- рый определяется формулой С = b(f)/b(F), где b(f), b(F) – число бит, необходимых для сохранения соответственно дискретно заданной функции f и аппроксиманта F. Задача приближенного восстановления значений дискретно заданной функции на «неосвещенных замерами» участках (обратная задача) возникает, как правило, когда значения функции f получены только в некоторых точках Nx,,x,x 21 из области определения S , и которых оказывается недостаточно для проведения даль- нейших исследований. В таком случае применяется способ приближенного представ- ления функции f аналитическим выражением с целью его использования для вычис- ления недостающих значений функции в других точках из S . На практике необходи- мость решения этой задачи возникает, когда при исследовании соответствующих процессов и объектов получение дополнительных данных затруднено или вообще невозможно, например, при исследовании природных процессов, а также при пере- ходе от нерегулярной сетки к регулярной для картографо-математического модели- рования в географических информационных системах (ГИС’ах). Задача сглаживания экспериментальных данных возникает в случаях, когда функция f задана на сетке S своими значениями, которые могут иметь значитель- ные случайные погрешности измерений. В случае, когда предварительно известны свойства поведения исходной функции, используется способ сглаживания экспери- ментальных данных с целью устранения указанных погрешностей. Чебышевский способ аппроксимации для аналитической обработки данных. Наиболее распространенными на практике для аналитической обработки данных являются методы и алгоритмы приближения функций, которые основываются на различных способах аппроксимации, а именно: интерполяционном, среднеквадра- тичном и равномерно-чебышевском. По сравнению с интерполяционным и среднеквадратичным способами прибли- жения способ наилучшей чебышевской аппроксимации является наиболее эффектив- ным и универсальным и обладает особенным свойством не только получать высокую Наилучшая чебышёвская аппроксимация как эффективный способ обработки… «Штучний інтелект» 3’2009 55 2К точность аппроксимации в точках дискретного представления функциональных зависимостей, но и обеспечивать требуемую гарантированную точность приближе- ния во всех точках непрерывного интервала их задания [4]. Проблема наилучшей (равномерной) чебышевской аппроксимации функции  xf на интервале  ba, основана на чебышевском принципе минимизации величины меры равномерного приближения        AxHxfHL nbaxn ;max ,   и состоит в нахож- дении такого аппроксиманта степени n с набором коэффициентов  naaaA ,,, 10  из всей совокупности аппроксимантов Hn степени n , который удовлетворяет усло- вию минимакса   minnHL , где  xf – непрерывная на  ba, функция и  n H HL n min  наименьшее возможное значение меры равномерного приближения. В качестве  AxH n ; будем рассматривать классы nP всех полиномов степени не выше n вида    AxPxaxP n n i i in ; 0   и классы nr всех дробно-рациональных выра- жений порядка n = l+m вида        BAxrxQxPxr nmln ;;/  , где Pl(x) и Qm(x) – поли- номы степеней l и m с наборами соответственно коэффициентов   liaA i ,0,  и   mjbB j ,0,  . Тогда постановка задачи нахождения наилучших чебышевских аппроксимантов имеет следующий вид:         nPnnbax PLAxPxf min;max ,   ,       xLPL nn Pn min , (1)         nr nn bax rLBAxrxf min;;max ,   ,       xRLrL nn rn min , (2) где Пn(x) и Rn(x) – полиномиальный и дробно-рациональный наилучшие чебышевские аппроксиманты, а  и  – соответственно величины их наилучших приближений. Существование, единственность и свойства наилучших аппроксимантов выте- кают из классических теорем Э. Бореля и П.Л. Чебышева – для полиномиальных и Н.И. Ахиезера и П.Л. Чебышева – для дробно-рациональных аппроксимантов [5]. На основании этих теорем единственные решения задач (1) и (2) совпадают соответ- ственно с решениями «элементарных» задач вида       AxPxf nXx ;max 1 ,       BAxrxf nXx ;;max 2 (1’), (2’) на таких (n+2)-точечных подмножествах  b,aX ,X 21  , для которых величины  и  достигают свои наибольшие возможные значения, равные  и  . Каждая из таких (n+2)-точечных задач называется задачей чебышевской интер- поляции функции f(x) на множестве (n+2)-х точек, которые являются соответственно чебышевским альтернансом для полиномиальной задачи (1) и экстремальным бази- сом для дробно-рациональной задачи (2). Именно это «замечательное» свойство «чебышевского альтернанса» является теоретической основой для нахождения всех наилучших чебышевских приближений. Все известные способы решения чебышевской задачи можно в основном разде- лить на способы, основанные на распространении методов Е.Я. Ремеза (особенно 2-го), и способы, использующие аппараты линейного и выпуклого программирования. Для Каленчук-Порханова А.А. «Искусственный интеллект» 3’2009 56 2К решения дробно-рациональной задачи используются также различные приемы после- довательной дифференциальной линеаризации по параметрам-коэффициентам. Син- тезом многих направлений в последние годы явилась также теория сплайновой ап- проксимации [5]. Преимуществами методов Е.Я. Ремеза являются сравнительно быстрая ско- рость их сходимости (в некоторых случаях квадратичная) и возможность стандар- тизации вычислений, что очень важно для эффективности их численных реализаций. Метод Е.Я. Ремеза решения задач (1) и (2) основан на последовательных чебышевских интерполяциях (п.ч.и.), r шагов которых сводятся к нахождению последовательности (n+2)-точечных S-наборов    1,0,  nvxS r vr , сходящейся к искомому чебышевскому альтернансу или экстремальному базису, и решению на каждом j-м шаге систем алгебраических уравнений         j vj vjn j v xPxf  1, , (3)                j vj vjm j vjl j v j v xQxPxfxw  1/ ,, (4) соответственно линейных относительно коэффициентов nkak ,0,  полинома  xP jn, и величины j в задаче (3) и нелинейных относительно коэффициентов liai ,0,  и mibi ,0,  и величины j в задаче (4), x Sj, 1,0  n . Следует заметить, что в отличие от полиномиального случая сходимость чебы- шевских интерполяций в случае задачи (4) теоретически обеспечивается не при любом начальном наборе (n+2)-х точек, хотя практика применения известных в литературе различных численных реализаций даже упрощенных вариантов метода Ремеза пока- зала крайне редкую их «несходимость». Основная трудность всех численных реализаций п.ч.и. состоит в выборе (n+2)- точечных подмножеств области аппроксимации, на которых осуществляются шаги чебышевских интерполяций. От способа этого выбора зависит не только скорость сходимости всего метода, но и сам факт его сходимости. Возможны три класса ва- риантов последовательной замены указанных (n+2)-точечных наборов: оптимальный, полуоптимальный и допустимый варианты. При оптимальном варианте для некоторых классов функций обеспечивается квад- ратичная скорость сходимости, что на практике обеспечивает, как правило, всего одну-две итерации. В полуоптимальном варианте – число итераций для получения аналогичного эффекта оказывается в несколько раз больше, а в допустимом оно может быть во много раз большим [2, с. 79]. Алгоритмы реализации способа наилучшей чебышевской аппроксимации. Разработанные в ИК им. В.М. Глушкова НАНУ алгоритмы основаны на втором ме- тоде п.ч.и. Е.Я. Ремеза и обладают рядом преимуществ по сравнению с известными в литературе аналогичными численными реализациями [6]. Главным достоинством этих алгоритмов является то, что в них разработан оптимальный способ замены (n+2)- точечных наборов при переходе к новому S набору [7]. Численная реализация разработанных алгоритмов также имеет ряд дополнитель- ных преимуществ, связанных с оптимизацией этих алгоритмов по точности и быстро- действию [8]. Алгоритмы могут находить либо аппроксимант заданной фиксирован- ной степени (вход по степени), либо такой аппроксимант, который обеспечивает Наилучшая чебышёвская аппроксимация как эффективный способ обработки… «Штучний інтелект» 3’2009 57 2К заданную точность приближений (вход по точности), которую не должна превышать апостериорная оценка полной погрешности аппроксимации по соответствующему алго- ритму. При этом при исследовании поведения функции отклонения       A;xFxfxw  во всех точках множества S на каждом шаге чебышевских интерполяций учиты- вается как верхняя, так и нижняя границы величины наилучшего приближения, что позволяет получить более точную оценку полной погрешности алгоритмов. Для решения полиномиальной задачи разработаны два алгоритма («А» и «Б»), соответствующие записям аппроксимирующего полинома в формах   n i i i xa 0 для алго- ритма «А» и    n i ii xTb 0 для алгоритма «Б». Алгоритм «Б» возник как модификация алгоритма «А» в связи с работой Н.С. Бах- валова [9] и может быть использован как существенное улучшение алгоритма «А», так как используемая в алгоритме «А» привычная запись полинома в виде   n i i i xa 0 в случаях большого «разброса» значений коэффициентов ia может стать источником большой погрешности округлений при вычислении значений полинома в точках по схеме Горнера. Предлагаемый Н.С. Бахваловым алгоритм использует запись многочле- нов в виде линейной комбинации многочленов Чебышева, а именно       n i iin xTbxQ 0 , и позволяет существенно уменьшить указанную погрешность при вычислений значе- ний полинома. В результате анализа полных погрешностей алгоритмов «А» и «Б» установлено, что преимущество алгоритма «Б» становится ощутимым при степенях 0n ; при 0n оба эти алгоритма примерно равносильны. Алгоритмы могут работать как для случая аналитически заданной, так и для случая дискретно заданной функции  xf . В обоих случаях процедура выбора (n+2)- точечного набора на каждом шаге ч.и. предполагает дискретизацию, поэтому отли- чие этих случаев только в том, что во втором из них значения функции в нужных точках известны, а в первом предусматривается процедура их вычисления. Дробно-рациональную аппроксимацию целесообразно использовать для повы- шения точности приближения функции  xf , природа которой такова, что она на некоторых участках имеет «всплески». В этом случае удается более точно учитывать особенности поведения функции. В силу того, что переход от полиномов к дробно-рациональным выражениям расширяет класс чебышевских аппроксимантов, очевидно, что nn  , где n и n – соответственно величины наилучшего дробно-рационального и полиномиального приближений той же функции на том же самом отрезке аппроксимации E . Несмотря на то, что переход от полиномиальных аппроксимантов к дробно- рациональным не позволяет увеличить порядок стремления к нулю величины n для всего класса функций, можно утверждать, что благодаря этому переходу расши- ряется класс функций, для которых величина наилучшего приближения будет того же порядка, что и для «хороших» функций. Каленчук-Порханова А.А. «Искусственный интеллект» 3’2009 58 2К Следует заметить, что в отличие от полиномиального случая сходимость п.ч.и. (причем, как правило, квадратическая) для дробно-рациональной задачи согласно рабо- там А. Ральстона [5] может быть обеспечена только при условии наличия начального приближения   xRn 0 , «близкого» к наилучшему дробно-рациональному аппрокси- манту  xRn . В некоторых частных случаях для многих математических функций, в особен- ности при малых значениях kmn  , в качестве начального набора точек для нахож- дения   xRn 0 можно применять точки уклонения полинома Чебышева, но для общего случая чебышевской рациональной задачи нет никаких практических рекомендаций относительно выбора «близкого»   xRn 0 . Этот недостаток устранен работами Вер- нера [5], который предложил метод, всегда сходящийся с любого начального при- ближения. Однако громоздкость вычислений и низкая скорость сходимости (линейная), по утверждению самого автора, не позволяют использовать его эффективно на практике. Учитывая сказанное выше, а также то, что даже упрощенные варианты п.ч.и. зачастую сходятся, автором был разработан сочетающий в себе преимущества методов Ремеза и Вернера комбинированный алгоритм (к.а.) [5]. Идея этого алгоритма состоит в том, что на практике часто желательно получить приближение, модуль-максимум уклонения которого не превышает некоторое заданное число 0 . Поэтому естественно вычислять последовательность аппроксимантов, начиная с более малых значений степеней l и m и повышая эти значения до получения при- ближения с желаемой точностью. Таким образом, будем предполагать, что всегда перед началом вычисления  xR m,l уже получен наилучший аппроксимант  xR m,l 11  . Для получения аппроксимантов каждой новой степени вначале используется метод п.ч.и. с обязательной проверкой сходимости алгоритма на каждом шаге ч.и. В случаях, когда сходимость не нарушается, метод п.ч.и. работает до конца, т.е. до получения наилучшего аппроксиманта текущей степени. Если же на каком-то шаге п.ч.и. сходимость нарушается (например, число участков перемены знака уклонений меньше 2 ml ), то для получения начального приближения    xR m,l 0 , имеющего не меньше 2 ml экстремума, вступает в работу начальный алгоритм (н.а.) метода Вернера. После этого снова работает метод п.ч.и. Если не учитывать случаи вы- рождения, сходимость метода п.ч.и. обеспечена и абсолютное значение максималь- ного уклонения полученного наилучшего аппроксиманта не превышает величину желаемой точности, то алгоритм заканчивает свою работу. В противном случае сте- пень аппроксиманта повышается и снова начинает работать метод п.ч.и. В разработанном к.а. учитываются случаи вырождения, когда у наилучшего аппроксиманта предыдущей степени уклонений равной величины и чередующих знак больше 2 ml , и почти вырождения, когда участков перемены знака больше 2 ml , а модуль-максимумов уклонений равной величины точно 2 ml . Несмотря на то, что случаи вырождения и особенно почти вырождения крайне редки, очень важно с вычислительной точки зрения уметь их распознавать до начала вычисления вырожденного аппроксиманта. С этой целью в алгоритме предпо- лагается, что перед вычислением  xR m,l всегда имеется наилучший аппроксимант  xR m,l 11  . Это равносильно тому, что вычисления следует начинать всегда с невырож- денных аппроксимантов  xR ,ml 0 для ml  , или  xR lm, 0 для ml  . Наилучшая чебышёвская аппроксимация как эффективный способ обработки… «Штучний інтелект» 3’2009 59 2К В случае дробно-рациональной аппроксимации исходная функция  xf пред- полагается заданной на  ba, как аналитически, так и дискретно, однако при поиске новых экстремумов уклонений используется дискретная процедура вычисления зна- чений  xf в точках. В отличие от полиномиального случая, когда вход в алгоритм может начинаться либо по заданной точности, либо по степени, вход в к.а. осущест- вляется только по заданной точности  . Отличие также состоит в том, что в этом случае система 2 ml алгебраических уравнений является нелинейной. Для ее ре- шения используется прием линеаризации и метод секущих. Когда для текущего  xR m,l п.ч.и. не сходится, т.е. число NN модуль-макси- мумов экстремумов, чередующих знак и равных по величине, меньше 2 ml ; или не сходится метод секущих, то начинает работать н.а. с наилучшего аппроксиманта  xR m,l 11  , последовательно повышая его степени до степеней текущего аппрокси- манта до тех пор пока не будет получено не менее 2 ml точек, в которых экстремумы уклонения чередуют знак. После этого снова начинает работать метод п.ч.и. до получения аппроксиманта, имеющего 2 ml равных по модулю и чере- дующих знак экстремумов-уклонений. Этот аппроксимант принимается за начальное приближение    xR m,l 0 метода п.ч.и. для нахождения наилучшего приближения  xR m,l , и работа к.а. продолжается до получения наилучшего аппроксиманта требуемой точ- ности. Следует добавить, что использование описанных выше алгоритмов полино- миального приближения позволяет находить также наилучшие равномерные прибли- жения некоторыми нелинейными выражениями, например, экспоненциальными  n nxaxaexpa 10 , логарифмическими   0 1- 1- axaxaln n n n n   и др., для которых доказаны соответствующие обменные теоремы и получены формулы для пересчета параметров приближения [10]. Для построения наилучшего равномерного приближения функции многих ( k ) пе- ременных   Xf  kx,,xf 1 , которая задана на множестве N точек     NX,,X 1 , обобщенными полиномами       n i iin XaXF 1  используется метод, который явля- ется аналогом метода п.ч.и. Е.Я. Ремеза решения задачи наилучшего чебышевского приближения путем сведения этой задачи к задаче линейного программирования с неотрицательными коэффициентами [5], [11]. В соответствующем алгоритме реализуются прямая и двойственная задачи линейного программирования. При этом главная задача – двойственная, решается модифицированным симплекс-методом с учетом того, что на практике количество уравнений N значительно больше коли- чества неизвестных n , и таблица «расширенного базиса» размера  42  n,n при мо- дифицированном симплекс-методе существенно меньше опорной таблицы  N,n 2 прямого симплекс-метода. Для большего повышения эффективности алгоритма и его оптимизации по точности и скорости симплекс-таблица заменяется сжатой (более чем вдвое), но равноценной по поданной информации таблицей, которая уже содер- жит допустимое базисное решение. Кроме этого, в процессе решения двойственной задачи реализуется полуоптимальный вариант перехода от одного допустимого базис- ного решения к следующему. Каленчук-Порханова А.А. «Искусственный интеллект» 3’2009 60 2К В некоторых случаях, особенно при приближении на больших отрезках, целе- сообразно использовать кусочные приближения. При таком приближении, благодаря разбиению всего отрезка аппроксимации  , на сегменты  ii t,t 1 ( r,i 1 ,  rttt 10 ) и приближении отдельно на каждом из них заданной функ- ции f наилучшим равномерным аппроксимантом *F , желаемая точность приближе- ния может быть обеспечена при меньших значениях степени этого аппроксиманта [10]. На протяжении многих лет автором в Институте кибернетики НАН Украины ведутся работы по алгоритмизации методов Е.Я. Ремеза, оценке всех видов погреш- ностей этих алгоритмов и по созданию соответствующих программных средств [1], [3-8], [10], [12]. Для разработанных алгоритмов и их программных реализаций автором полу- чены оценки всех видов погрешностей, а именно погрешности постановки задачи за счет дискретного представления аппроксимируемой функции, неустранимой и вы- числительной погрешностей алгоритмов, а также полной абсолютной погрешности решения этих задач. Это позволило значительно повысить точность результатов вычислений (в некоторых случаях на порядок) [8]. Наряду с общепринятой схемой оценки полной погрешности (п.п.) [13] автором предложена также вторая схема оценки п.п., которая использует известные априорные сведения о структурных свойст- вах функции, в частности о ее принадлежности к определенному классу. При этом получены неулучшаемые для некоторых классов функций как априорные, так и апостериорные мажорантные детерминированные оценки всех видов погрешнос- тей, расчеты которых включены в вычислительные схемы алгоритмов и программ. Для определения значений указанных оценок п.п. решения чебышевской за- дачи автором были получены представляющие самостоятельный интерес вспомога- тельные результаты из конструктивной теории функций, в том числе уточняющие известные оценки венгерских авторов. С целью существенного повышения эффективности разработанных вычисли- тельных алгоритмов осуществлялись также различные процедуры для их моди- фикации, в том числе реализован подход, основанный на применении сегментной (кусочной) аппроксимации разными классами аппроксимантов. Главное преимущество разработанных автором алгоритмов заключается в том, что с целью повышения их эффективности проведена оптимизация по быстродей- ствию и по точности. Оптимизация по быстродействию достигается за счет следующих факторов:  алгоритмы основаны на методе последовательных чебышевских интерполяций (п.ч.и.) Е.Я. Ремеза и относятся к алгоритмам подъема, при работе которых нижняя граница выбранных на каждом шаге (n+2)-х максимальных уклонений от функции аппроксиманта порядка n не уменьшается на последующих шагах, что делает их предпочтительнее по скорости сходимости;  в алгоритмах также реализуется на практике один из трех возможных, а именно оптимальный вариант последовательной замены (n+2)-точечных наборов, на кото- рых осуществляются шаги ч.и., что обеспечивает квадратичную скорость сходимос- ти всего итерационного процесса и позволяет получать результат за 2 – 3 итерации;  комбинированный алгоритм реализации дробно-рациональной аппроксимации поз- воляет обеспечить сходимость п.ч.и. также и для дробно-рационального случая, при этом сохраняются действия факторов оптимизации для полиномиального случая. Наилучшая чебышёвская аппроксимация как эффективный способ обработки… «Штучний інтелект» 3’2009 61 2К Оптимизация по точности осуществляется благодаря:  включению в вычислительную схему алгоритмов расчета как априорных, так и апостериорных оценок полной погрешности, что позволяет корректировать получен- ные результаты, а именно в зависимости от требуемой точности менять степень поли- нома, число точек сетки, параметр критерия останова и обоснованно выбирать вид аппроксиманта;  просмотру при исследованиях поведения уклонений полинома от функций на каж- дом шаге итерации при переходе к следующему шагу всех точек сетки, при этом учи- тываются как верхняя, так и нижняя границы величины наилучшего приближения;  использованию на каждом шаге чебышевских интерполяций для решения систем линейных алгебраических уравнений метода Краута, для которого проведена опти- мизация по точности;  применению в алгоритме дробно-рациональной аппроксимации на каждом j-м шаге ч.и. для решения нелинейной системы уравнений относительно коэффициентов и вели- чины наилучшего приближения специального подхода, основанного на линеаризации системы и использовании метода секущей;  использование схемы Н.С. Бахвалова вместо схемы Горнера для уменьшения пог- решности округлений при вычислениях в точках значений полиномов степени боль- ше 10;  применению кусочно-полиномиальной аппроксимации для сжатия больших и сверхбольших массивов числовых данных, что значительно повышает точность при- ближения и обеспечивает высокие коэффициенты сжатия по сравнению с аппрокси- мацией без разбиения на сегменты. В алгоритмах применялись также дополнительные приемы повышения их эф- фективности:  решение задач аппроксимации как для дискретно, так и для аналитически задан- ных функций, при этом дополнительно вводится процедура вычисления значений функции в точках дискретизации;  проведение предварительной аппроксимации с целью повышения точности значе- ний дискретных данных в случаях, когда известны свойства исходной аппроксими- руемой функции;  обеспечение двух «входов» в алгоритмы, что позволяет находить либо аппрокси- мант заданной фиксированной степени («вход» по степени), либо такой, который обеспечивает заданную точность приближения («вход» по точности);  использование различных классов аппроксимирующих выражений, наиболее соот- ветствующих характеру поведения («природе») приближаемой функции;  построение полиномиального приближения с произвольным весом   0xw ;  проверка в комбинированном алгоритме решения дробно-рациональной задачи перед началом каждой следующей итерации возможности появления случаев вырож- дения или почти вырождения, когда не удается получить нужное количество точек экстремального базиса. Эти случаи в алгоритме распознаются до начала вычислений вырожденного аппроксиманта, после чего подключаются средства для их устра- нения;  применение для аппроксимации функций многих переменных модифицирован- ного симплекс-метода и некоторых процедур, которые обеспечивают значительное уменьшение количества вычислений и повышение точности результатов. Каленчук-Порханова А.А. «Искусственный интеллект» 3’2009 62 2К Выводы Аппарат аппроксимации на протяжении многих лет использовался в составе прикладного программного обеспечения отечественных ЭВМ и применялся для сжа- тия массивов данных при решении различных прикладных задач (в том числе для оборонных целей), при расчётах характеристик сложных динамических систем, например, при расчёте прочностных характеристик летательных аппаратов для НИИ им. Туполева, расчетах траекторий движения искусственных спутников, транссект и кривых трансконтинентальных переносов загрязнений воздушной среды, токовых состояний водных систем (водоемов, водотоков, Черного моря) в связи с последст- виями Чернобыльской катастрофы и др. В процессе применения аппарата наилучшей чебышевской аппроксимации была не только подтверждена его высокая эффективность, но и проводилось дальнейшее усовершенствование. Более подробная информация о работах содержится в приво- димых ссылках. В результате численной реализации алгоритмов аппроксимации были разра- ботаны программные комплексы на языках программирования ФОРТРАН, Алгол, Паскаль, а также на С++ для отечественного суперкомпьютера с кластерной архи- тектурой СКИТ. В состав прикладного программного обеспечения СКИТ включены две библиотеки программ: библиотека чебышевской аппроксимации функций одной и многих переменных и библиотека для вычисления с повышенной точностью значений элементарных и специальных функций. Аппарат чебышевской аппроксимации в последнее время применялся для сжа- тия больших одномерных массивов-векторов (с возможным количеством значений до 10 млн чисел) с целью получения небольшого числа параметров аппроксимантов. В результате расчётов были получены большие значения коэффициентов сжатия (в среднем более двух порядков). Эти работы выполнялись в рамках создания Под- системы аппроксимации для сжатия больших массивов числовых данных в составе Информационно-аналитической системы «Бюджетный комитет», а также в рамках научно-технического проекта по разработке программно-технических комплексов для решения расчётных задач АНТК «Антонов». В настоящее время для СКИТ разрабатывается пакет программ аппроксимации функций одной и многих переменных разными способами приближения: интерполя- ционным, среднеквадратичным и чебышевским [12], который войдет в состав его Базового прикладного программного обеспечения. Этот пакет имеет ряд существен- ных преимуществ по сравнению с известными аналогичными пакетами и специали- зированными библиотеками, такими, например, как Mathcad, Maple, MATLAB, Mathe- matica, MATHLIB, NETLIB. Алгоритмы и соответствующие им программные реализации построения наи- лучших чебышёвских приближений функций одной и нескольких переменных использовались на протяжении многих лет для аналитической обработки массивов данных в разных направлениях науки и техники, в том числе для оборонной тема- тики. В последние годы аппарат чебышёвской аппроксимации широко применяется в рамках научно-технического проекта по разработке программно-технических комп- лексов для решения расчётных задач АНТК «Антонов», а также для сжатия больших и сверхбольших массивов-векторов с возможным количеством значений до 10 млн Наилучшая чебышёвская аппроксимация как эффективный способ обработки… «Штучний інтелект» 3’2009 63 2К чисел, что позволяет получать на практике большие значения коэффициентов сжатия (в среднем два порядка). Программные комплексы на основе разработанных алго- ритмов включены в состав прикладного программного обеспечения суперкомпью- тера СКИТ с кластерной архитектурой [3]. Литература 1. Каленчук-Порханова А.А. Аппарат аппроксимации для анализа и синтеза сложных систем / А.А. Кален- чук-Порханова // Пр. Міжнар. конф. «50 років Інституту кібернетики ім. В.М. Глушкова НАН України». – Київ, 2008. – С. 354-361. 2. Ремез Е.Я. Основы численных методов чебышевского приближения / Ремез Е.Я. – К. : Наук. думка, 1969. – 623 с. 3. Каленчук-Порханова А.А. Об одном алгоритме полиномиальной чебышевской аппроксимации / А.А. Каленчук-Порханова // Оптимизация вычислительных методов. – К. : Ин-т кибернетики АН УССР, 1974 . – С. 45-51. 4. Иванов В.В. Об эффективности алгоритмов полиномиальных и дробно-рациональных чебышевских приближений / В.В. Иванов, А.А. Каленчук // Конструктивная теория функций. – София, 1983. – С. 72-77. 5. Каленчук-Порханова А.А. Аппроксимация функций одной и многих переменных / А.А. Каленчук- Порханова // Численные методы для многопроцессорного вычислительного комплекса ЕС. – М. : Изд-во ВВИА им. Н.Е. Жуковского, 1987. – С. 366-395. 6. Каленчук-Порханова А.А. Алгоритмы и анализ погрешности наилучшей чебышевской аппроксима- ции одной переменной / А.А. Каленчук-Порханова // Теория приближения функций : тр. Междунар. конф. теории приближения функций, (Калуга, 1975). – М., 1977. – С. 213-218. 7. Каленчук-Порханова А.А. Наилучшая чебышевская аппроксимация – алгоритмы и их применение / А.А. Каленчук-Порханова // Сб. трудов Международного симп. «Питання оптимізації обчислень». – Киев, 2009. 8. Каленчук-Порханова А.А. Алгоритмы реализации наилучшей чебышевской аппроксимации – повы- шение их эффективности // Сб. трудов Международного симп. «Питання оптимізації обчислень» – Киев, 2009. 9. Бахвалов Н.С. Численные методы / Бахвалов Н.С. – М. : Наука, 1973. – 631с. 10. Каленчук-Порханова А.А. Аппарат аппроксимации в составе программного обеспечения суперком- пьютера с кластерной архитектурой / А.А. Каленчук-Порханова, Л.П. Вакал // Искусственный интеллект. – 2009. – № 1. – С. 158-165. 11. Александренко В.Л. Алгоритм построения приближённого равномерно-наилучшего решения систе- мы несовместных линейных уравнений / В.Л. Александренко // Алгоритмы и алгоритмические языки. – М. : ВЦ АН СССР, 1968. – Вып. 3. – С. 57-74. 12. Каленчук-Порханова А.А. Пакет программ аппроксимации функций / А.А. Каленчук-Порханова, Л.П. Вакал // Комп’ютерні засоби, мережі і системи. – 2008. – № 7. 13. Воеводин В.В. Ошибки округления и устойчивость в прямых методах линейной алгебры / В.В. Вое- водин. – М. : ВЦ МГУ, 1969. А.О. Каленчук-Порханова Найкраща чебишовська апроксимація як ефективний спосіб обробки інформації Розглядається проблема найкращої чебишовської апроксимації для ефективної обробки інформації. Наводяться обґрунтування переваг алгоритмів апроксимації, що пов’язано з їх оптимізацією за точністю та швидкодією. А. Kalenchuk-Porkhanova The Best Chebyshev’s Approximation for Effective Treatment of Information The problem of the best Chebyshev’s approximation for effective treatment of information is considered. The advantages of the algorithms elaborated which are connected with their accuracy and performance optimization are presented. Статья поступила в редакцию 30.07.2009.
id	nasplib_isofts_kiev_ua-123456789-8018
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-11-29T14:15:16Z
publishDate	2009
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Каленчук-Порханова, А.А. 2010-04-26T15:28:12Z 2010-04-26T15:28:12Z 2009 Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации / А.А. Каленчук-Порханова // Штучний інтелект. — 2009. — № 3. — С. 53-63. — Бібліогр.: 13 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8018 519.651.2 Рассматривается проблема наилучшей чебышевской аппроксимации для эффективной обработки инфор- мации. Дается обоснование преимуществ разработанных алгоритмов аппроксимации, которые связаны с их оптимизацией по точности и быстродействию. Розглядається проблема найкращої чебишовської апроксимації для ефективної обробки інформації. Наводяться обґрунтування переваг алгоритмів апроксимації, що пов’язано з їх оптимізацією за точністю та швидкодією. The problem of the best Chebyshev’s approximation for effective treatment of information is considered. The advantages of the algorithms elaborated which are connected with their accuracy and performance optimization are presented. ru Інститут проблем штучного інтелекту МОН України та НАН України Интеллектуальный анализ данных Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации Найкраща чебишовська апроксимація як ефективний спосіб обробки інформації The Best Chebyshev’s Approximation for Effective Treatment of Information Article published earlier
spellingShingle	Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации Каленчук-Порханова, А.А. Интеллектуальный анализ данных
title	Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации
title_alt	Найкраща чебишовська апроксимація як ефективний спосіб обробки інформації The Best Chebyshev’s Approximation for Effective Treatment of Information
title_full	Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации
title_fullStr	Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации
title_full_unstemmed	Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации
title_short	Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации
title_sort	наилучшая чебышёвская аппроксимация как эффективный способ обработки информации
topic	Интеллектуальный анализ данных
topic_facet	Интеллектуальный анализ данных
url	https://nasplib.isofts.kiev.ua/handle/123456789/8018
work_keys_str_mv	AT kalenčukporhanovaaa nailučšaâčebyševskaâapproksimaciâkakéffektivnyisposobobrabotkiinformacii AT kalenčukporhanovaaa naikraŝačebišovsʹkaaproksimacíââkefektivniisposíbobrobkiínformacíí AT kalenčukporhanovaaa thebestchebyshevsapproximationforeffectivetreatmentofinformation

Наилучшая чебышёвская аппроксимация как эффективный способ обработки информации

Institution

Similar Items