ММ-6. ДИСКРЕТИЗАЦИЯ ФУНКЦИОНАЛЬНОГО ПРОСТРАНСТВА

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

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

1. В области некоторого пространства задано уравнение

, (4.1)

где : - оператор (в общем случае – нелинейный); - искомый элемент; - нулевой элемент.

Оператор зависит от своего аргумента : ; например, коэффициенты системы канонических уравнений зависят от усилий (в методе сил) или от деформаций (в методе перемещений), Мы будем этот факт отражать записью воздействия такого оператора на элемент в виде ; всё уравнение (4.1) тогда приобретёт вид

. (4.2)

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

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

2. В каждой подобласти некоторого пространства, в которой разыскивается приближённое решение, выбирается «нулевое приближение» - первый элемент последовательности решений. Это достаточно трудная задача, так как он должен быть достаточно близок к точному решению, которое неизвестно. Обычно (но не всегда!) существует некоторая область, включающая точное решение, из любой точки которой может стартовать вычислительный процесс, порождающий сходящуюся к точному решению последовательность приближённых решений.

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

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

, (4.2)

причём на первом шаге .

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

Следовательно, эти задачи линейны, так как задано и оператор задан и не зависит от .

Все вычисления при фиксированном значении , а также само решение уравнения (4.2), называются - ой итерацией.

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

На каждой итерации проверяется выполнение условия выхода из итерационного цикла– некоторая оценка погрешности(см. лекцию ММ-1) не должна превышать определённую заранее допустимую величину.

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

Как указывалось в лекции ММ-1, такое сведение нелинейной задачи к последовательности линейных задач (и их решений) называется линеаризацией.

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

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

Настоящая лекция посвящена простейшему методу линеаризации – методу простых итераций.

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

, (4.3)

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

Идея метода чрезвычайно проста. Выбирается начальное приближение и критерий выход из цикла(обеспечивающий достаточную точность приближения) , после чегоначинается выполнение итераций где - процедура проверки возможности выхода из цикла если , то можно прекратить итерации и принять . Напоминаем: так как точное решение неизвестно, точная мера погрешности решения , где - номер последней выполненной итерации, не может быть определена. Определяется лишь оценка величины , по которой, как мы установим далее, можно при выполнении определённых условий определить оценку меры погрешности. Таким образом, в результате применения этого метода мы получаем последовательность приближённых решений ; необходимо ответить на вопросы: а) сходится ли эта последовательность? б) если сходится, то к точному решению или нет? в) когда прекратить выполнение итераций?

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

Вначале введём некоторые определения.

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

4.2. Неподвижная точка оператора (Адрес файла Блок 4_____) Неподвижной точкой оператора называется элемент , удовлетворяющий условию . Вернитесь к тексту

Для того, чтобы метод простых итераций сходился, необходимо выполнение определённых условий. В общем случае это условие достаточно неопределённо: должно быть выбрано достаточно «близко» к (в то время, как неизвестно!), и представляет интерес: каково множество таких элементов, которые можно выбирать в качестве начального приближения, то - есть, таких точек, для которых последовательность решений сходится к ?

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

4.6. Оператор сжатия (Адрес файла Блок 4__________) Пусть оператор , где - метрическое пространство или его подмножество. Он называется оператором сжатия, если имеется такая постоянная , что . Вернитесь к тексту

к оператору задачи

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

Теперь мы можем сформулировать теорему Банаха о неподвижной точке в метрическом пространстве

Теорема Банаха. Пусть - полное метрическое пространство и оператор является оператором сжатия. Тогда этот оператор имеет единственную неподвижную точку (решение уравнения ), которая может быть найдена методом простых итераций. Начальный элемент может быть выбран в нём произвольно.

Лемма.. . (4.4)

Доказательство леммы. Умножим левую часть (4.4) на

(здесь в первых скобках записана первая сумма, во вторых скобках – вторая). Разделив теперь первое и последнее выражения на , мы получим равенство, которое и требовалось доказать.

Доказательство теоремы. По условию теоремы, заданное пространство – полное. Следовательно, для того, чтобы установить наличие предела, достаточно доказать, что последовательность фундаментальна. Для этого исследуем поведение при . Согласно аксиоме треугольника

(4.5)

Дадим оценку расстояния между двумя последовательными элементами :

Итак,

(4.6)

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

(4.7)

Используя доказанное в лемме равенство (4.4) для вычисления , приведём правую часть (4.7) к виду

(4.8)

Теперь мы можем проверить, является ли при выполнении условий теоремы последовательность сходящейся (здесь учтено, что и ):

. (4.9)

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

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

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

.

При это неравенство может выполняться только при , то – есть, при .

Добавления.

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

2. Оценка погрешности - го приближения может быть получена по формуле

, (4.10)

где - константа Липшица оператора .

3. Из (4.10) легко получить количество итераций, гарантирующее, что погрешность не будет превосходить заданную величину (с учётом )

. (4.11)

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

(4.12)

и оценки (4.10) в сочетании с требованием

. (4.13)

Из (4.13) непосредственно следует

. (4.14)

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

. (4.15)

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

	4.7. Метод простых итераций для операторного уравнения (Адрес файла Блок 4_______) Методом простых итераций для операторного уравнения называется следующая последовательность вычислительных процедур. 1. Проверка возможности использования метода. 2. Выбор начальной точки. 3. Последовательное выполнение итераций, причём любая - ая итерация выполняется по формуле . 4. Условия выхода из цикла могут иметь следующий вид: , , . Вернитесь к тексту

Если необходимо решить нелинейное уравнение, то – есть, уравнение (4.3) имеет вид

, (4.16)

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

, (4.17)

где .

Тогда для каждого при любой его длине константа Липшица в его пределах

. (4.18)

При его концы сближаются и , откуда в пределе

, (4.19)

где .

Для всего отрезка , поэтому в качестве константы Липшица можно принять

. (4.20)

Тогда условие выхода из цикла (4.15) приводится к виду

. (4.21)

В случае решения одного нелинейного уравнения возможны два варианта модификации теоремы Банаха.

Вариант 1. Пусть на нелинейная функция удовлетворяет условию Липшица с и . В этом случае уравнение (4.16) имеет единственное решение и .

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

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

В случае, если решается система нелинейных уравнений с неизвестными,

(4.22)

или в компактной векторно – матричной записи

, (4.23)

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

Исходя из этого, введём в рассмотрение матрицу Якобиуказанной выше совокупности функций :

. (4.24)

Другое обозначение матрицы Якоби

. (4.25)

По

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

. (4.26)

Таким образом, мы вместо одного числа, которому можно было бы приписать роль константы Липшица, имеем чисел.

Для преодоления этой трудности нам потребуется ввести понятие нормы матрицы. Здесь для нас важна роль матрицы как оператора в выражении для дифференциала вектор – функции

. (4.27)

Поэтому дадим вначале более общее понятие нормы линейного оператора.

ример расчёта.ана система уравнений

4.9 Норма линейного оператора (Адрес файла Блок 4_______) Нормой линейного оператора , где - нормированное пространство, называется наименьшее из таких чисел , для которых выполняется условие   ,   где и - нормы элемента и его образа . Можно показать, что . Вернитесь к тексту

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

если норма вектора принимается равной , то

, (4.28)

если норма вектора принимается равной , то

можно применять два варианта определения нормы матрицы

1) норма Шмидта (иногда называется евклидовой, а также сферической)

; (4.29)

2) спектральная норма – определяется как наибольшее собственное число матрицы

Теперь мы можем определить константу Липшица для матрицы - оператора :

. (4.30)

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

Решение системы (4.22) методом простых итераций заключается в многократном повторении вычислений по формуле

, (4.31)

где - номер итерации.

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

. (4.32)

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

Пример.

Требуется найти решение системы

с допустимой погрешностью .

1. Локализуем корень системы. Из первого уравнения и неравенств следует, что . В этом диапазоне , и второе уравнение даёт .

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

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

Итак, применение метода простых итераций возможно.

Условие выхода из цикла

3. Назначим начальное приближение (трудоёмкие прикидки отвлекли бы нас от основной идеи лекции, поэтому опущены): .

4. Организуем модифицированный итерационный цикл

.

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

4.3. Критерии усвоения

После изучения содержания данной темы Вы должны:

·

как решаются методом простых итераций нелинейные уравнения и системы нелинейных уравнений;

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

как контролируется погрешность очередной итерации;

· понимать

роль каждого условия применения метода;

смысл алгоритма решения на каждой итерации;

· Уметь

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

4.4. Выход темы в другие темы и дисциплины

Данная тема имеет выход в дипломные, магистерские и диссертационные работы.

4.5. Тест - контроль для самопроверки

4.1. Что называется линеаризацией нелинейной задачи?

А. Следующая последовательность процедур:

1. Проверка выполнения условий применения данной итерационной схемы.

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

3. Выполнение итераций, включающих

- формулирование линейной задачи - ой итерации;

- решение этой задачи с использованием результатов предыдущей итерации (предыдущих итераций);

- проверка условий выхода из итерационного цикла;

- при выполнении указанных условий – выход из цикла.

Б. Формулирование линейной задачи - ой итерации.

В. Формулирование и решение линейной задачи - ой итерации с использованием результатов предыдущей итерации (предыдущих итераций).

Г. Преобразование нелинейной задачи в линейную задачу.

4.2. Что называется неподвижной точкой оператора?

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

,

где и - нормы элемента и его образа .

Б. Элемент , удовлетворяющий условию , где - заданный оператор, - нулевой элемент.

В. Элемент , удовлетворяющий условию .

Г. Элемент .такой, что , где - заданный оператор.

4.3. Что такое область сходимости неподвижной точки оператора ?

А. Область , если для каждой точки существует элемент .

Б. Область , если для каждой точки можно указать такой элемент , что .

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

Г. Множество всех элементов такое, что для любого последовательность сходится к .

4.4. Что называется оператором сжатия?

А. Оператор , удовлетворяющий условию , где - нулевой элемент.

Б. Оператор , удовлетворяющий условию , если .

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

Г. Оператор , для которого можно указать постоянную такую, что .

4.5. Что называется методом простых итераций?

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

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

2. Выбор начальной точки.

3. Последовательное выполнение итераций, причём любая - ая итерация выполняется по формуле .

4. Условия выхода из цикла могут иметь следующий вид:

,

,

.

Б. Следующая последовательность вычислительных процедур:

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

2. Выбор начальной точки.

3. Последовательное выполнение итераций, причём любая - ая итерация выполняется по формуле .

4. Условия выхода из цикла могут иметь следующий вид:

,

,

.

В. Следующая последовательность вычислительных процедур:

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

2. Выбор начальной точки.

3. Последовательное выполнение итераций, причём любая - ая итерация выполняется по формуле .

4. Условия выхода из цикла могут иметь следующий вид:

,

,

.

Г. Следующая последовательность вычислительных процедур:

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

2. Выбор начальной точки.

3. Последовательное выполнение итераций, причём любая - ая итерация выполняется по формуле .

4. Условия выхода из цикла могут иметь следующий вид:

,

,

.

Ответы на тест – самоконтроль 4.5 (Адрес файла Блок 3______) 4.1-«А» Следующая последовательность процедур: 1. Проверка выполнения условий применения данной итерационной схемы. 2. Разделение корней (выделение подобластей, включающих единственный корень) и выбор нулевых приближений для каждой подобласти.. 3. Выполнение итераций, включающих - формулирование линейной задачи - ой итерации; - решение этой задачи с использованием результатов предыдущей итерации (предыдущих итераций); - проверка условий выхода из итерационного цикла; - при выполнении указанных условий – выход из цикла. 4.2- «В» Элемент , удовлетворяющий условию . 4.3.- «В» Множество всех элементов такое, что для любого последовательность принадлежит ей. 4.4- В. Оператор , для которого можно указать постоянную такую, что . 4.5- А. Следующая последовательность вычислительных процедур. 1. Проверка возможности использования метода. 2. Выбор начальной точки. 3. Последовательное выполнение итераций, причём любая - ая итерация выполняется по формуле . 4. Условия выхода из цикла могут иметь следующий вид: , , .

А. Следующая последовательность процедур:

1. Проверка выполнения условий применения данной итерационной схемы.

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

3. Выполнение итераций, включающих

- формулирование линейной задачи - ой итерации;

- решение этой задачи с использованием результатов предыдущей итерации (предыдущих итераций);

- проверка условий выхода из итерационного цикла;

- при выполнении указанных условий – выход из цикла

ММ-6. ДИСКРЕТИЗАЦИЯ ФУНКЦИОНАЛЬНОГО ПРОСТРАНСТВА.

Дата добавления: 2014-04-15; просмотров: 489; Нарушение авторских прав

Мы поможем в написании ваших работ!