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

Очень часто в различных областях физики, техники, экономики и т.д. приходится встречаться с математическими задачами, для которых не удается найти решение классическими методами или решения выражены громоздкими формулами, которые не приемлемы для практического использования. Поэтому большое значение приобрели итерационные методы. В большинстве случаев итерационные методы являются приближенными, так как с их помощью обычно решаются задачи, аппроксимирующие исходные. В ряде случаев итерационный метод строится на базе бесконечного процесса, который в пределе сводится к искомому решению. Однако реально предельный переход не удается осуществить, и процесс, прерванный на некотором шаге, дает приближенное решение. Кроме того, источниками погрешности являются несоответствие математической модели изучаемому реальному явлению и погрешность исходных данных [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) отделяет точки, в которых определяется новая информация, от точек, информация в которых уже использовалась [16].

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

Мы подошли к важному понятию порядка ИФ. Пусть последовательность 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)

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

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

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

откуда следует, что

Но последнее противоречит предположению о том, что порядок равен .

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

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

(1.15)

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

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

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

(1.16)

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

В отличие от многих авторов, основывающихся на этом определении, мы предпочтем представить его в виде утверждения теоремы 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) сходится к этому решению. Вследствие специального вида этих условий доказательство будет простым. Существует много других доказательств подобных утверждений как для вещественных функций, так и для абстрактных пространств, использующих различные предположения [26].

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

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

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

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

(1.25)

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

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

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

что невозможно.

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

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

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

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

Из условия Липшица следует, что

Таким образом, и .

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

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

(1.26)

Пусть и - произвольные положительные целые числа. Тогда

поэтому

Учитывая (1.26), получаем, что

Или

(1.27)

Пусть . Тогда

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

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

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

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

Поэтому потребуем, чтобы

(1.28)

Отметим, что

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

(1.29)

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

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

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

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

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

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

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

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

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

Тогда

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

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

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

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

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

; .

Кроме того, .

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

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

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

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

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

, (1.30)

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

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

(1.31)

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

 (1.32)

В самом деле, пусть (1.32) выполнено для некоторого номера . Тогда

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

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

Пусть, кроме того, и соотношение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 (1.33)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 1 - а) график функции; б) график зашумленной функции

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

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

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

Пусть корень - простой. Для близких к значений справедливо приближенное равенство

Поэтому равенство (2) примет вид , откуда получаем

.

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

. (1.34)

Рисунок 2 - График функции при различных отклонениях

Здесь - число, которое в рассматриваемой задаче играет роль абсолютного числа обусловленности.

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

. (1.35)

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

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

.

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

.

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

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

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

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

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

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

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

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

(1.36)

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

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

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

,

, (1.37)

…………………

,

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

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

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

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

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

, (1.38)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В данной работе предлагается способ построения итерационной формулы основанный на аппроксимации с помощью полинома Бернштейна [2]. Считается, что функция 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%

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