Обобщения полиномов Бернштейна в задачах устойчивости нелинейных динамических систем

ДИПЛОМНАЯ РАБОТА

на тему:

" Обобщения полиномов Бернштейна в задачах устойчивости нелинейных динамических систем"

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

Исследованием динамических систем занимались такие отечественные и зарубежные ученые, как Ляпунов, Понтрякин, Четаев, Красовский, Аносов, Пуанкаре, Хайрер.

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

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

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

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

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

Точная и строгая формулировка понятия устойчивости применительно к состоянию равновесия динамической системы была дана выдающимся русским ученым A.M. Ляпуновым.

Предметом нашего анализа будут не объекты вообще, а динамические системы в математическом понимании этого термина.

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

Оценка устойчивости нелинейных систем приводит к задаче решения нелинейных уравнений и систем нелинейных уравнений. В работе предлагается вариант итерационного процесса для решения этих задач.

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

1. Основные понятия теории динамических систем

1.1 Описание динамических систем с помощью дифференциальных уравнений

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

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

Исследование реальных систем сводится к изучению математических моделей, совершенствование и развитие которых определяются анализом экспериментальных и теоретических результатов при их сопоставлении.

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

Различают непрерывные и дискретные операторы и соответственно системы с непрерывным и дискретным временем. Системы, для которых отображение с помощью оператора может быть определено для любых (непрерывно во времени), называют также потоками по аналогии со стационарным течением жидкости. Если оператор отображения определен на дискретном множестве значений времени, то соответствующие динамические системы называют каскадами или системами с дискретным временем.

Динамические системы называются автономными, если они не подвержены действию внешних сил, переменных во времени.

Рассмотрим динамические системы, моделируемые конечным числом обыкновенных дифференциальных уравнений. Применительно к таким системам сохранились представления и терминология, первоначально возникшие в механике. В рассматриваемом случае для определения динамической системы необходимо указать объект, допускающий описание состояния заданием величин в некоторый момент времени t = t₀. Величины x_i могут принимать произвольные значения, причем двум различным наборам величин x_i отвечают два разных состояния. Закон эволюции динамической системы во времени записывается системой обыкновенных дифференциальных уравнений.

Если рассматривать величины как координаты точки x в n — мерном пространстве, то получается наглядное геометрическое представление состояния динамической системы в виде этой точки, которую называют изображающей, а чаще фазовой точкой, а пространство состояний — фазовым пространством динамической системы. Изменению состояния системы во времени отвечает движение фазовой точки вдоль некоторой линии, называемой фазовой траекторией.

Необходимо уточнить взаимосвязь понятий числа степеней свободы и размерности фазового пространства динамической системы. Под числом степеней свободы понимается наименьшее число независимых координат, необходимых для однозначного определения состояния системы. Под координатами первоначально понимались именно пространственные переменные, характеризующие взаимное расположение тел и объектов. В то же время для однозначного решения соответствующих уравнений движения необходимо помимо координат задать соответствующие начальные значения импульсов или скоростей. В связи с этим система с m степенями свободы характеризуется фазовым пространством в два раза большей размерности (n = 2m).

Теория динамических систем, основана на дифференциальных уравнениях вида

, (1.1)

где — динамические переменные;

— функции (в общем случае нелинейные), описывающие их (в смысле динамических переменных) взаимодействие в данной точке пространства;

— характерные времена изменения переменных ;

член описывает распространение динамических переменных в пространстве.

В частном случае, когда все динамические переменные распределены в пространстве равномерно, мы имеем систему обыкновенных дифференциальных уравнений:

, (1.2)

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

Интуитивное представление об устойчивости (или неустойчивости) есть у каждого. Неустойчиво, например, состояние карандаша, поставленного на острие; неустойчиво движение шарика по гребню. В то же время движение его по ложбине устойчиво. Более точное представление дает анализ уравнений движения (и / или стационарных состояний). Этот анализ основан на исследовании поведения малых отклонений от соответствующего решения. Продемонстрируем это на примере стационарных состояний точечной системы. Стационарными являются состояния, соответствующие таким значениям переменных, при которых все функции равны нулю. При этом значения не меняются со временем, поскольку все производные также равны нулю. Однако малые отклонения от стационарных значений меняются со временем, и их изменение можно описать системой линейных дифференциальных уравнений

(1.3)

где .

Решения имеют вид:

(1.4)

Здесь — коэффициенты, пропорциональные начальным отклонениям; они малы в меру малости последних. Величины — числа, которые являются решениями алгебраического уравнения:

(1.5)

где — символ Кронекера =1, i=j; =0, i? j.

Величины называются также числами Ляпунова и играют главную роль в анализе устойчивости. Если все числа Ляпунова отрицательны, то состояние устойчиво. Действительно, в этом случае все отклонения со временем уменьшаются, т. е. система стремится обратно к стационарному состоянию, даже если ее немного отклонить от него. Если хотя бы одно из чисел Ляпунова положительно, то состояние неустойчиво. Действительно, тогда отклонения возрастают со временем, причем достаточно быстро. В общем случае числа Ляпунова могут быть комплексными. Устойчивость определяется тогда знаком реальной части. Если среди чисел Ляпунова имеются равные нулю или чисто мнимые, то стационарное состояние называется нейтральным; при отклонении от него не появляются ни возвращающие, ни отклоняющие силы.

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

(1.6)

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

Подчеркнем важное свойство: числа Ляпунова являются характеристическими (или собственными) числами системы; они не зависят от начальных условий. Таким образом, устойчивость (или неустойчивость) — внутреннее свойство исследуемой системы, а не результат внешнего воздействия. Особенность его в том, что проявляется оно только при наличии малых внешних воздействий. Эта особенность привела к важным методологическим последствиям. Сейчас приходится пересматривать и подвергать ревизии некоторые, казалось бы, установившиеся в физике понятия.

1.2 Методы решения нелинейных уравнений и систем нелинейных уравнений

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

Как известно, многие скалярные уравнения не всегда имеют аналитическое решение, в этом случае используются итерационные методы с заданной степенью точности: задача приближенного вычисления нуля функции f (x), или что, то же самое, задача приближенного вычисления корня уравнения f (x)=0. Термины нуль функции f, корень уравнения f (x)=0 и решение уравнения f (x)=0 будут использоваться как эквивалентные. По-видимому, у рассматриваемой задачи нет общепризнанного точного названия. В самом деле, термин решение уравнения охватывает и решение дифференциальных уравнений. Прилагательные алгебраическое и трансцендентное обычно используются для различения случаев, когда f соответственно является или не является многочленом. Представляется, что наиболее подходящим термином для данной задачи является термин поиск корней.

Независимая переменная указывается или не указывается явно в зависимости от того, идет ли речь о функции или о значении функции в некоторой точке из области определения. Учитываются и соображения удобства чтения формул. Таким образом, обозначения f и f (x) будут использоваться как равноправные.

Производные функции f будут обозначаться либо через f^(l), либо через f^ґґfЅ…, причем f⁽⁰⁾= f. Если f^ґґ не обращается в нуль в окрестности точки б и производная f^(l) непрерывна в этой окрестности, то у f существует обратная функция F, производная F^(l) которой непрерывна в некоторой окрестности нуля.

Нуль б имеет кратность m, если f (x)=(x-б)^mg (x), причем функция g (x) ограничена в окрестности точки б и g (б)? 0.

Будем предполагать, что m — целое положительное число. Если m=1, то б называется простым нулем; если же m > 1, то б называется кратным нулем.

Пусть x_i, x_i-1, …x_i-n — набор из n+1 точек, являющихся приближениями к решению б, а выбор x_i+1 полностью определяется информацией, полученной в точках x_i, x_i-1, …x_i-n. Обозначим через ц функцию, задающую соответствие между набором x_i, x_i-1, …x_i-n и точкой очередного приближения x_i+1, т. е.

x_i+1= ц (x_i, x_i-1, …x_i-n) (1.7)

Определенную таким образом функцию ц будем называть итерационной функцией. В дальнейшем вместо термина «итерационная функция» как в единственном, так и во множественном числе будет использоваться аббревиатура ИФ.

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

В основу классификации ИФ положим характер использования ими информации.

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

Последнюю будем называть старой, или ранее вычисленной информацией. Предположим, что выбор x_i+1 определяется только новой информацией в точке x_i, а ранее вычисленная информация не используется. Тогда

x_i+1 = ц (x_i), (1.8)

а ц называется одноточечной ИФ.

Наиболее известным примером ИФ этого рода является ИФ Ньютона.

Пусть теперь выбор x_i+1 определяется новой информацией в точке x_i и ранее вычисленной информацией в точках x_i+1,…, x_i-n. Тогда

x_i+1 = ц (x_i; x_i-1, …x_i-n) (1.9)

а ц называется одноточечной ИФ с памятью.

Символ «;» в (1.9) отделяет точку x_i, в которой вычисляется новая информация, от точек, информация в которых уже использовалась. Наиболее известным примером одноточечной ИФ с памятью является ИФ метода секущих.

Пусть выбор x_i+1 определяется на основе новой информации в точках x_i, щ₁(x_i), …, щ_k(x_i), где k? 1, а ранее вычисленная информация не используется.

Тогда

x_i+1 = ц (x_i; щ₁(x_i), …, щ_k(x_i)), (1.10)

а ц называется многоточечной ИФ. Среди многоточечных ИФ нет широко известных.

Наконец, обозначим z_j, набор из k+1 чисел x_j; щ₁(x_j), …, щ_k(x_j), где k? 1. Если

x_i+1 = ц (z_i; z_i-1, …, z_i-n), (1.11)

то ц называется многоточечной ИФ с памятью. Как и в (1.9), символ «;» в (1.11) отделяет точки, в которых определяется новая информация, от точек, информация в которых уже использовалась.

Широко известных примеров многоточечных функций с памятью не существует.

Мы подошли к важному понятию порядка ИФ. Пусть последовательность x₀, x₁,…, x_i, … сходится к б. Положим e_i = x_i — б. Если существует действительное число p и ненулевая константа C, такие, что

| e_i+1| / | e_i | > C (1.12)

то p называется порядком последовательности, а C — константой асимптотики погрешности.

Установим связь между порядком последовательности {x_i} и порождающей ее ИФ.

Для этого представим (1.12) в виде

(1.13)

Если существуют вещественное p и ненулевая константа С, удовлетворяющие (1.13), то приписываем ИФ ц порядок p независимо от того, сходится порождаемая ею последовательность или нет.

Ясно, что если последовательность сходится, то порядок итерационной функции и порядок порожденной ею последовательности совпадают. Единственность порядка будет установлена ниже.

Принадлежность ц классу ИФ, имеющих порядок p, будет обозначаться

(1.14)

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

Прилагательные линейный и квадратичный будут иногда использоваться вместо первый и второй.

Заметим, что если порядок существует, то он единствен. В самом деле, пусть сходящаяся последовательность имеет два порядка: и, причем Тогда откуда следует, что, Но последнее противоречит предположению о том, что порядок равен .

Ниже будет показано, что ИФ с памятью не могут быть целого порядка.

Если производная непрерывна и

(1.15)

то ц имеет порядок и .

Уравнение (1.15) можно переписать в виде:

В классической работе E. Schroder, относящейся к 1870 г., дано следующее определение порядка: ц имеет порядок, если

(1.16)

Это определение имеет смысл только для ИФ одной переменной, имеющих непрерывных производных.

В отличие от многих авторов, основывающихся на этом определении, мы предпочтем представить его в виде утверждения теоремы 1.

Для достижения поставленных целей нам потребуется мера информации, используемой ИФ, и эффективности ИФ.

В качестве измерителя информации естественно принять объем информационного запроса d (informational usage), выражаемый количеством элементов новой информации, используемой в каждой итерации.

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

Принадлежность ц классу ИФ порядка с объемом информационного запроса d будем обозначать посредством

(1.17)

Меру эффективности определим следующим образом: эффективность использования информации EFF равна частному от деления порядка на объем информационного запроса, т. е.

(1.18)

Другое определение эффективности выглядит так:

(1.19)

Величина (1.19) названа индексом эффективности.

Одноточечные ИФ и одноточечные ИФ с памятью вычисляют только одно новое значение каждой производной или вычисляются первые производных, то объем информационного запроса равен s, а устойчивость динамический берштейн аппроксимация

(1.20)

Предположим, что одноточечная ИФ использует старую информацию в n точках. Положим

(1.21)

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

Иногда последовательность и отдельные ее члены будут обозначаться одним и тем же символом; при этом смысл обозначения будет ясен из контекста.

Рассмотрим решение уравнения

(1.22)

при помощи итерации

(1.23)

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

(1.24)

Очевидно, есть решение уравнения тогда и только тогда, когда — неподвижная точка функции .

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

Предположим, что функция ц определена на некотором замкнутом ограниченном интервале и принимает значения из этого интервала. Тогда, если принадлежит, то и все принадлежат. Для существования решения уравнения (1.22) нужно предполагать непрерывность ц. А именно, справедлива Лемма 1. Пусть ц — непрерывная функция, действующая из в. Тогда существует такое, что .

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

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

(1.25)

для производных точек и из. Заметим, что это сжимающее условие Липшица обусловливает непрерывность. Покажем, что при этом условии решение уравнения единственно.

Лемма 2. Пусть — функция, действующая из в и удовлетворяющая сжимающему условию Липшица (1.25). Тогда уравнение имеет не более одного решения.

Доказательство. Предположим, что существуют два различных решения и. Следовательно,, и. Используя (1.25), получаем что невозможно.

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

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

Доказательство. Лемма 1 и 2 гарантируют существование и единственность решения б уравнения. Это решение и претендует на роль предела последовательности, определяемой соотношением. Очевидно, Из условия Липшица следует, что Таким образом, и .

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

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

(1.26)

Пусть и — произвольные положительные целые числа. Тогда поэтому Учитывая (1.26), получаем, что Или

(1.27)

Пусть. Тогда

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

Выше для решения уравнения использовалась итерационная процедура. Для задач, которые мы будем рассматривать в дальнейшем, это нетипично. В общем случае нам предстоит иметь дело с итерационным_уравнением вида и для него строить функционал, выполняющий роль ИФ. Показано, что если ц удовлетворяет сжимающему условию Липшица, то итерационная последовательность сходится к единственному решению задачи о неподвижной точке. В дальнейшем будем уделять больше внимания не поиску слабых достаточных условий, обеспечивающих сходимость итерационной последовательности, а построению таких ИФ, для которых эта последовательность сходится быстро.

При этом мы будем готовы потребовать выполнения гораздо более сильных условий, чем условие Липшица. В частности, будем предполагать, что в рассматриваемом интервале имеет нуль.

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

(1.28)

Отметим, что где расположено в промежутке между и б. Используя (1.28), получаем

(1.29)

Потребуем, чтобы в некоторой окрестности точки б выполнялось условие .

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

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

Только что доказанный результат можно сформулировать так: если производная непрерывна в окрестности точки б, для которой и, то является точкой притяжения.

Далее, пусть. Тогда не обращается в нуль в некоторой окрестности точки б. Положим; при этом (1.29) примет вид, ясно, что если и не обращается в нуль, то и отлично от нуля для любого конечного номера .

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

Следовательно, и. Это — случай сходимости первого порядка, или линейной сходимости.

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

В дополнение к условию предположим теперь, что производная, непрерывна.

Тогда где точка расположена в промежутке между и б. Ясно, что имеет порядок только в том случае, если, а .

В этом случае, где .

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

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

Тогда имеет порядок в том и только том случае, если

; .

Кроме того, .

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

Достаточные условия сходимости этой последовательности будут установлены ниже.

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

Проводимые ниже рассуждения охватывают случаи как сверхлинейной, так и линейной сходимости.

Исходным моментом наших рассуждений является соотношение

(1.30)

Положим. Предположим, что производная непрерывна на и соотношение выполнено для всех из. Из условия следует, что. Поэтому

Предположим, что

(1.31)

Тогда. Следовательно,. Докажем по индукции, что при выполнении (1.31) для всех справедливо

(1.32)

В самом деле, пусть (1.32) выполнено для некоторого номера. Тогда Следовательно, (1.32) выполнено и для, что завершает индукцию. Поскольку, то. Таким образом, теорема доказана.

Теорема 3. Предположим, что производная непрерывна на интервале .

Пусть, кроме того, и соотношение выполняется для всех из, причем. Тогда для любого и .

Пусть производная непрерывна в окрестности точки б и имеет первый порядок.

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

Существенность последнего условия иллюстрирует пример

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

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

Это только одно из целого ряда преимуществ сверхлинейной сходимости над линейной.

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

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

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

Задачу нахождения решений скалярных уравнений можно сформулировать различными способами.

Например, как задачу на нахождение корней: f (x)=0, или как задачу на нахождение неподвижной точки: F (x)=x.

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

Итак, задача отыскивания корней нелинейного уравнения с одним неизвестным вида

(1.33)

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

Корень уравнения (1.33) называется простым, если. В противном случае (т.е. в случае) корень называется кратным. Целое число назовем кратностью корня, если для и. Геометрический корень соответствует точке пересечения графика функции с осью. Корень является простым, если график пересекает ось под ненулевым углом, и кратным, если пересечение происходит под нулевым углом.

Уточним постановку задачи. В конкретной задаче часто интерес представляют не все корни уравнения, а лишь некоторые из них. Тогда постановку задачи уточняют, указывая на то, какие из корней подлежат определению (положительные корни, корни из заданного интервала, максимальный из корней и т. д.).

В подавляющем большинстве случаев представить решение уравнения (1.27) в виде конечной формулы оказывается невозможным. Невозможность найти точное решение нелинейного уравнения кажется огорчительной. Однако нужно признать, что желание найти точное числовое значение решения вряд ли следует считать разумным. Во-первых, в реальных исследованиях зависимость является лишь приближенным описанием, моделирующим истинную связь между параметрами и. Поэтому точное решение уравнения (1.33) все равно является лишь приближенным значением того параметра x, который в действительности соответствует значению. Во-вторых, даже если уравнение (1.33) допускает возможность нахождения решения в виде конечной формулы, то результат вычислений по этой формуле почти с неизбежностью содержит вычислительную погрешность и поэтому является приближенным.

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

Решение задачи отыскания корней нелинейного уравнения осуществляют в два этапа. Первый этап называется этапом локализации (или отделения) корней, второй — этапом итерационного уточнения корней. Отрезок, содержащий только один корень уравнения (1.33), называют отрезком локализации корня .

Цель этапа локализации считают достигнутой, если для каждого из подлежащих определению корней удалось указать отрезок локализации (его длину стараются по возможности сделать минимальной).

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

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

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

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

Очень важно рассмотрение обусловленности задачи вычисления корня уравнения.

Пусть — корень уравнения (1.33), подлежащий определению. Будем считать, что входными данными для задачи вычисления корня являются значения функции в малой окрестности корня.

Так как значения будут вычисляться на ЭВМ по некоторой программе, то в действительности задаваемые значения являются приближенными и их следует обозначать через .

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

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

Будем предполагать, что в достаточно малой окрестности корня выполняется неравенство, где

где — граница абсолютной погрешности.

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

На рисунке 1, а представлена идеальная ситуация, отвечающая исходной математической постановке задачи, а на рисунке 1, б — реальная ситуация, соответствующая вычислениям значений функции на ЭВМ.

Рисунок 1 — а) график функции; б) график зашумленной функции Если функция непрерывна, то найдется такая малая окрестность корня, имеющая радиус, в которой выполняется неравенство .

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

Будем называть этот интервал интервалом неопределенности корня. Найдем оценку величины .

Пусть корень — простой. Для близких к значений справедливо приближенное равенство Поэтому равенство (2) примет вид, откуда получаем

.

Следовательно,

. (1.34)

Рисунок 2 — График функции при различных отклонениях Здесь — число, которое в рассматриваемой задаче играет роль абсолютного числа обусловленности.

Действительно, если — корень уравнения, то и тогда выполнено неравенство

. (1.35)

Заметим, что радиус интервала неопределенности прямо пропорционален погрешности вычисления значения. Кроме того, возрастает (обусловленность задачи ухудшается) с уменьшением, т. е. с уменьшением модуля тангенса угла наклона, под которым график функции пересекает ось (рисунок 2, а, б).

Если же (т.е. корень — кратный), то формула (1.35) уже не верна. Пусть кратность корня равна. Тогда в силу формулы Тейлора справедливо приближенное равенство, в правой части которого все слагаемые, кроме последнего, равны нулю. Следовательно, неравенство (1.34) имеет вид

.

Решая его, получаем аналогично (1.35) оценку радиуса интервала неопределенности:

.

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

Отметим, что не может быть меньше величины — погрешности представления корня в ЭВМ.

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

Во-первых, не имеет смысла ставить задачу о вычислении корня с точностью .

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

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

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

Если вдали от интервала неопределенности величина

(1.36)

обычно бывает меньше единицы, то появление при некотором значения свидетельствует, скорее всего, о начале «разболтки» — хаотического поведения итерационной последовательности. В этой ситуации вычисления имеет смысл прервать, чтобы выяснить причину явления и принять правильное решение.

Лучшим из полученных приближений к решению следует считать, конечно,. Использование для контроля вычислений величины (1.36) называют часто правилом Гарвика.

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

(1.37)

…

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

Однако на практике она встречается значительно чаще, так как в реальных исследованиях интерес представляет, как правило, определение не одного, а нескольких параметров (нередко их число доходит до сотен и тысяч).

Найти точное решение системы, т. е. вектор, удовлетворяющий уравнениям (1.37), практически невозможно.

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

Будем считать функции непрерывно дифференцируемыми в некоторой окрестности решения. Введем для системы функций матрицу Якоби которая будет использована в дальнейшем.

(1.38)

Основные этапы решения. Как и в случае уравнения с одним неизвестным, отыскание решений начинаются с этапа локализации. Для каждого из искомых решений указывают множество, которое содержит только одно это решение и расположено в достаточно малой его окрестности. Часто в качестве такого множества выступает параллелепипед или шар в m-мерном пространстве.

Иногда этап локализации не вызывает затруднений; соответствующие множества могут быть заданными, определяться из физических соображений, из смысла параметров либо быть известными из опыта решений подобных задач. Однако чаще всего задача локализации (в особенности при больших m) представляет собой сложную проблему, от успешного решения которой в основном и зависит возможность вычисления решений системы (1.37). На этапе локализации особое значение приобретают квалификация исследователя, понимание им существа решаемой научной или инженерной проблемы, опыт решения этой или близких задач на ЭВМ.

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

На втором этапе для вычисления решения с заданной точностью используют один из итерационных методов решения нелинейных систем.

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

Корректность и обусловленность задачи. Будем считать, что система (1.37) имеет решение, причем в некоторой окрестности этого решения матрица Якоби невырождена. Выполнение последнего условия гарантирует, что в указанной окрестности нет других решений системы (1.37).

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

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

Аналогично, погрешности в вычислении вектора-функции приводят к появлению области неопределенности D, содержащей решение системы (1.37) такой, что для всех векторное уравнение удовлетворяется с точностью до погрешности. Область D может иметь довольно сложную геометрическую структуру.

Мы удовлетворимся только лишь оценкой радиуса этой области.

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

Тогда можно приближенно оценить с помощью неравенства .

Таким образом, в рассматриваемой задаче роль абсолютного числа обусловленности играет норма матрицы, обратной матрице Якоби .

1.3 Численные алгоритмы решения нелинейных уравнений

Многочлены в форме Бернштейна были описаны Сергеем Натановичем Бернштейном в 1912 году и использованы им в конструктивном доказательстве аппроксимационной теоремы Вейерштрасса.

С развитием компьютерной графики, полиномы Бернштейна, заключённые в промежуток x [0, 1], стали играть важную роль при построении кривых Безье.

При натуральном n алгебраический полином

(1.39)

называется полиномом в форме Бернштейна или просто полиномом Бернштейна. Очевидно, что

. (1.40)

Базисными полиномами Бернштейна от одной переменной называются полиномы:

, n = 0, 1, …

Базисные полиномы обладают следующими свойствами:

при x (0, 1) и всех k = 0, 1,…, n; (1.41)

(1.42)

Лемма 1. При всех вещественных x справедливо равенство:

(1.43)

Доказательство. Равенство (1.37) достаточно проверить при x є (0, 1). Имеем

.

Вместе с тем,. Значит, .

Теперь продифференцируем тождество (1.43). Получим

.

Отсюда и из (1.42) следует (1.43).

Теорема 1. Справедлива формула

(1.44)

где .

Доказательство. Имеем

=+=+

++=.

Мы воспользовались тем, что при k (1, n-1).

Преобразование (1.44) можно продолжить:

где и т. д. В результате получим

.

Таким образом, выведено рекуррентное соотношение

i=1, …, n, k=0,1,…, n-i;, k = 0, 1,…, n,

которое позволяет вычислить значение в фиксированной точке x (0, 1).

Перепишем формулу (1.39) в виде

.

С учетом свойств (1.41) и (1.42) коэффициентов заключаем, что число B (x) при фиксированном x? (0, 1) есть выпуклая комбинация чисел y₀, y₁,…, y_n. Рекуррентное соотношение (1.44) представляет собой быстрый способ вычисления этой выпуклой комбинации.

Рассмотрим двумерный случай.

Базисные полиномы Бернштейна от двух переменных определяются следующим образом:

, , n = 0, 1, …,

где — так называемые триномиальные коэффициенты.

В частности,

, , ;

; ,, ;

; ,, .

При

Отметим также, что при

Справедливо тождество

(1.45)

Оно следует из общей формулы

(Здесь мы воспользовались тем фактом, что .)

Подставив в (1.45), получим

1. Рассмотрим полином от двух переменных в форме Бернштейна Введём конечные разности на треугольном массиве коэффициентов Предложение 1. Полином допускает представление

(1.46)

Доказательство. Имеем Применив формулу (1.46) к, получим Поменяем порядок суммирования по и по (через). Поскольку

и ,

то Воспользуемся равенством Придем к требуемому представлению Предложение доказано.

2. Зафиксируем два целых неотрицательных числа и положим .

Предложение 2. Для частной производной полинома в форме Бернштейна при справедлива формула

(1.47)

где .

Доказательство.

Продифференцируем тождество (1.46) по. Учитывая, что, получаем, Но, так что Это соответствует формуле (1.47) при .

Далее Продифференцируем данное тождество по. Учитывая, что, аналогично предыдущему получаем Продолжив дифференцирование, придём к (1.47).

3. Рассмотрим треугольных массивов базисных полиномов Бернштейна

Положим для удобства

Например, при получим 15 искусственно добавленных полиномов.

Предложение 3. При любых вещественных справедливы рекуррентные соотношения

(1.47)

Доказательство. Перепишем тождества (1.46), заменив в них на :

(1.48)

Зафиксируем. При обе части. Пусть. Тогда При обе части (1.45) равны .

Аналогично проверяется случай .

Если, то, согласно (1.44),, так что Осталось рассмотреть случай. Имеем Мы воспользовались легко проверяемой формулой Предложение доказано.

4. Зафиксируем произвольные вещественные. Для вычисления значения введем треугольных массивов с помощью рекуррентных соотношений

(1.49)

Предложение 4. Справедливо равенство .

Доказательство. При утверждение тривиально. При оно проверяется так:

Пусть. Согласно (1.47), (1.48) и (1.49) имеем Продолжив аналогично, получим Предложение доказано.

5. Обратимся к вопросу о вычислении производных полинома. Нам потребуется соотношение

(1.50)

которое непосредственно следует из (1.49). Действительно, Предложение 5. При фиксированных частные производные от полинома в форме Бернштейна можно вычислить по формуле Здесь

Доказательство. Согласно (1.45)

Воспользуемся приёмом из доказательства и соотношением (1.50).

Запишем

Продолжив данное преобразование, получим Предложение доказано.

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

1.5 Применение полиномов Бернштейна для решения нелинейных уравнений

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

В данной работе предлагается способ построения итерационной формулы основанный на аппроксимации с помощью полинома Бернштейна. Считается, что функция f (x) определена на отрезке [0,1] и её значения заданы в ряде равноотстоящих точек x_i = i/n, i = 0, 1, 2, …, n.

Полином Бернштейна имеет вид

B_n(x) = f (k/n) C_n^k x^k(1-x)^n-k

Замена в исходном уравнении функции, её аппроксимацией, позволяет упростить задачу.

Уточнение значения корня осуществляется за счет увеличения количества узлов или степени полинома.

На основе вычислительного эксперимента выявлено влияние точности задания значений функции, количества узлов степени полинома на качество решения.

Проведен сравнительный анализ свойств предложенных итерационных формул, построенной на основе аппроксимационного полинома Бернштейна, с известной итерационной формулой.

Теоретическая оценка погрешности для трех равноотстоящих узлов:

e_n+1 ~C (e_n²-h²)

Рассмотрим тестовую задачу: решим с помощью итерационно формулы на основе аппроксимационных полиномов Бернштейна уравнение .

Построим функцию и ее приближение полиномом на одном графике:

Рисунок 3 — Графики функций и

Точное решение уравнения находим с помощью оператора solve среды Maple 11. Т.о. точное решение уравнения выглядит так: .

Запишем базисные многочлены Бернштейна второй степени:

.

.

Погрешность вычислений равна 0,02.

Теперь к исходному уравнению добавим случайную величину (погрешность) е, например шум: .

Рисунок 4 — График функции g (x) при е=0,1

Рисунок 5 — График функции g (x) при е=0,2

Рисунок 6 — График функции g (x) при е=0,5

С помощью Maple были проведены вычисления для всех трех случаев.

Получены следующие результаты (таблица 1, таблица 2, таблица 3):

Таблица 1 — Приближения к корню уравнения при е=10%

Таблица 2 — Приближения к корню уравнения при е=20%

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

Это выгодно отличает итерационную формулу, построенную на основе апроксимационного полинома Бернштейна от ряда классических итерационных методов: метод Ньютона, метод секущих и т. д.

Таблица 3 — Приближения к корню уравнения при е=30%

Также на качество решения не влияет количество узлов полинома.

1.7 Обобщенные полиномы Бернштейна в задаче оценки параметров системы

Если область, в которой находится корень системы является многогранником, обобщенные функции Бернштейна вводятся так:

;

Формулы для выпуклых комбинаций вершин выпуклого n-угольника:

Существует два способа для вычисления л_i.

Первый способ: 1) Разбиение области n — угольника с вершинами A_i(x_i, y_i), i= на треугольники. 2) В имеющейся n-угольной тонкой пластине выделим точку, являющуюся геометрическим центром фигуры, и найдем ее координаты по формуле: