1.3. Аппроксимация в задаче навигации. Сравнение различных методов аппроксимации

Информация о геофизическом поле предназначенная для записи на бортовой компьютер, обычно задается в виде таблиц заранее

измеренных значений поля в узлах достаточно густой сетки. Хранение таблиц требует больших объемов памяти. Так, информация о высоте земной поверхности предгорий и горных участков с большим числом вершин и впадин содержит сотни тысяч чисел.

Один из возможных способов преодоления этой трудности — приближение поля как функции географических координат посредством функции являющейся комбинацией элементарных функций. Вместо (1.3) на бортовом компьютере решается следующая задача

Тогда хранению подлежат коэффициенты этой функции а значения поля в конкретных точках определяются по мере надобности приближенно вычислением по координатам точек. Такой способ позволяет существенно сократить объем хранимой информации, однако может привести к увеличению, по сравнению с табличным способом, времени вычисления значения поля в точке.

Для использования этого способа предварительно необходимо

1) выбрать класс V функций, предназначенный для приближения геофизического поля,

2) определить метод поиска аппроксимирующей функции для конкретного геофизического поля.

Набор возможных классов V перечислен в 1. гл. Что касается методов поиска аппроксимирующей функции, то с учетом специфики задачи навигации естественно использовать следующие:

а) наилучшее приближение в метрике поля классом

б) наилучшее приближение поля классом V в норме

в) специальные методы, позволяющие минимизировать ошибку привязки.

Выбор метрики пространства обосновывается тем, что геофизическое поле может быть задано со случайными ошибками и при замере фрагмента могут появиться большие ошибки измерения. Выбор метрики диктуется оценкой (1.7) ошибки привязки через Наиболее привлекательны специальные методы минимизации ошибки привязки. В настоящем параграфе на примере поля высот земного рельефа сравниваются следующие методы аппроксимации:

L) билинейная интерполяция,

Р) кусочно-многочленная аппроксимация (разрывные сплайны) в

Т) кусочно-тригонометрическая интерполяция, кусочно-многочленная аппроксимация в с последующей интерполяцией,

S) аппроксимация параболическими В-сплайнами в Предположим, что непрерывная функция определена в прямоугольной области

и известны ее значения и узлах равномерной сетки

С шагом

Билинейная интерполяция на разреженной сетке. Зададим натуральное число и построим разреженную сетку

с шагом где целая часть числа а. Эта сетка разбивает область на частичные квадраты со стороной

Внутри каждого частичного квадрата приближающую функцию возьмем в виде интерполяционного многочлена 2-й степени

где

— интерполяционные многочлены 1-й степени по переменной

Тогда на области получим непрерывную кусочно-параболическую функцию

интерполирующую значения функции в узлах сетки

Р. Кусочно-многочленная аппроксимация степени Пусть натуральные числа. На каждом частичном квадрате

построим многочлен

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

В итоге, на области получим кусочно-многочленную функцию, аппроксимирующую исходную функцию Отметим, что эта функция на прямых терпит разрыв.

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

или

наилучшего среднеквадратического приближения.

Р. Кусочно-многочленная аппроксимация с последующей интерполяцией. Сравнение описанных аппроксимаций показывает, что метод позволяет строить непрерывную приближающую функцию, но на каждом квадрате использует значение функции лишь в вершинах квадрата и не учитывает информацию во внутренних узлах, поэтому при больших (начиная с некоторого) не может обеспечить требуемую точность аппроксимации. Методы , напротив, дают на каждом квадрате Пнаилучшую полиномиальную аппроксимацию, используя значения функции во всех точках сетки попавших в квадрат но построенная этим методом функция на области а точнее, на смежных сторонах частичных квадратов, не является непрерывной. Предлагаемый здесь метод является промежуточным, он в определенной мере объединяет полезные свойства методов .

Зададим три натуральных числа Построим квадраты размером где

и внутри каждого выделим квадрат размером

Рис. 2

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

Обозначим

Аппроксимирующую функцию на прямоугольной области, содержащей квадраты (см. рис. 2)

зададим формулой

где

Другими словами, совпадает с на квадрате на прямоугольниках определяется линейной интерполяцией значений двух соседних многочленов ветственно и билинейной интерполяцией значений четырех соседних многочленов в случае, когда точка принадлежит квадрату

Сплайн-аппроксимация. Зададим натуральное число с? и берем на оси абсцисс сетку узлов сплайна

и на оси ординат сетку

где номера выбраны из условий

В сетку включены через штук узлы исходной сетки и дополнительно два узла слева и два узла справа.

Аналогично устроена сетка Обозначим

Напомним, что параболическим -сплайном (см., гл. I, § 10) называется функция

где

Носителем функции является отрезок функция дифференцируема на всей оси, а ее график склеен из трех кусков парабол.

В качестве аппроксимирующей функции на области возьмем сплайн-функцию

реализующую минимум

Качество метода аппроксимации оценивается (см., гл. I, п. 1) с учетом

сложности вычисления аппроксимирующей функции, степени сжатия информации,

величины уклонения приближаемой и приближающей функции, точности привязки. Сложность вычисления аппроксимирующей функции существенно влияет на скорость решения задачи привязки. Она определяется числом используемых при вычислении функции в точке

операций: выделение целой части числа, вычисление функции выбор числа из таблицы. Для каждой из функций L, Р, Т, P, S вычисления начинаются с определения индексов соответствующего квадрата содержащего точку и выбора по из двумерной таблицы значения высоты либо коэффициентов полинома. Так, для билинейной интерполяции определяются

на что расходуется 2 операции взятия целой части числа, 2 операции и 2 операции и выбираются из исходной таблицы значения Приведем число операций, необходимых для вычисления самих функций. В приводимой ниже таблице - порядок многочленов на 11-,

Коэффициенты сжатия информации. Коэффициентом сжатия информации (будем обозначать его через С) называется отношение объемов памяти, необходимой для хранения исходной информации и сжатой информации. Для хранения как численног о значения высоты в точке, так и значения одного коэффициента приближающей функции требуется одинаковый объем памяти — один байт.

Область где содержит точек исходной сетки а прореженная сетка состоит из

точек, следовательно,

Прямоугольная область, образованная частичными квадратами где , содержит точек исходной сетки. Хранению подлежат коэффициенты многочленов: по коэффициентов и В тригонометрическом случае надо хранить также числа Учитывая это, получим

В том случае, когда наряду с коэффициентами полиномов в ЭВМ хранятся значения полиномов в вершинах квадратов (таких значений имеем

Полагая здесь получаем коэффициент сжатия для -методов.

Функция содержит - коэффициентов, поэтому

Подчеркнем, что в методе число элементарных операций одинаково для различных коэффициентов сжатия.

Приведем число элементарных операций для рассматриваемых методов при коэффициенте сжатия, близком к 30 и соответствующие этому коэффициенту сжатия величины среднеквадратических

уклонения а и ошибки привязки полученные в результате численных расчетов (см. следующий пункт):

где среднеквадратические ошибки привязки координат х, у.

Результаты численных расчетов. Перечисленными методами приближения была проведена аппроксимация двух участков рельефа земной поверхности: 1-й рельеф содержит как гладкие, так и гористые районы, его размеры рельеф гладкий, его размеры В обоих случаях шаг Полученные аппроксимирующие функции опробованы в задаче привязки по набору измеренных высот. Результаты расчетов иллюстрируются графиками (рис. 3), на которых С — коэффициент сжатия информации, а — величина среднеквадратического приближения, среднеквадратические ошибки привязки координат х, у по серии из 100 испытаний при случайных шумовых помехах.

Необходимо отметить, что правильный выбор метода сжатия информации (аппроксимации) является основой успешного решения задачи навигации. При выборе метода следует учитывать особенности исходной задачи, в частности, возможности ЭВМ (объем памяти, быстродействие) и характер приближаемой функции. Для каждого из предложенных методов, по-видимому, имеется класс поверхностей, на которых он дает лучшую (в сравнении с остальными) аппроксимацию

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

(кликните для просмотра скана)

Здесь наряду с точностью могут играть роль такие свойства приближающей функции, как непрерывность, дифференцируемость.

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