Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач icon

Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач



НазваниеБилет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач
Дата17.10.2016
Размер
ТипУроки, сочинения

Билет №17

№1


Метод релаксации. Методы Якоби и Гаусса-Зейделя.

Методы релаксации для решения граничных задач.


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


(4.1)


З
десь L – эллиптический оператор, а  - правая часть уравнения, тогда перепишем уравнение как уравнение диффузии:

( 4.2)


Начальное распределение u релаксирует к равновесному решению при T стремящемся к бесконечности. Уравнение диффузии для нашей задачи можно записать в виде:

( 4.3)

Если мы используем разностную схему FTCS, то получим:


(4.4)

Эта схема устойчива, если t/(*)1/2, в двумерном случае t/(*)1/4, возьмем максимально возможный шаг, при котором t/(*)=1/4, тогда уравнение (4.4) примет вид:



(4.5)


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

Второй классический метод называется методом Гаусса-Зейделя; этот метод используется в многосеточных методах решения граничных задач. В этом методе два значения неизвестной функции в правой части (4.5) берутся в момент времени n+1, как только они становятся известны.


(4.6)

Этот метод также медленно сходится, однако анализ этого метода может быть полезен.

Рассмотрим методы Якоби и Гаусса-Зейделя с точки зрения представления матриц в виде суммы. Заменим обозначение u на x, чтобы получить стандартный вид матричного уравнения.




(4.7)

Мы можем представить матрицу A в виде



(4.8)


Здесь –D –диагональная часть матрицы A, L – нижняя треугольная часть матрицы A, U – верхняя треугольная часть матрицы A, матрицы L, U содержат нули на диагонали. При использовании метода Якоби итерацию на r –м шаге можно записать в виде:

(
4.9)

Матрица –D-1*(L+U) – итерационная матрица при помощи которой находится следующее итерационное приближение. Была произведена для этого метода оценка числа итераций, необходимых для достижения точности 10-p


(4.10)

При увеличении размерности сетки J спектральный радиус ps стремится к единице. Для данного конкретного уравнения, граничных условий и геометрии сетки спектральный радиус, в принципе, можно вычислить аналитически, так для сетки размерности J*J с условиями Дирихле на всех четырех границах, асимптотическая формула для больших J имеет вид:

(
4.11)

При этом необходимое число итераций можно оценить по формуле:

(
4.12)

Другими словами, число итераций пропорционально числу точек сетки.

Методу Гаусса-Зейделя соответствует следующее матричное уравнение:

(
4.13)

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

(

4.14)

(4.15)

Метод SOR


Мы получим лучший алгоритм – один из самых распространенных до семидесятых годов прошлого века - если мы скорректируем величину x(r) на r-м шаге итераций Гаусса-Зейделя. Из метода Гаусса-Зейделя следует:

(
4.16)

Член в квадратных скобках –вектор невязки (r-1) т.е.

(
4.17)

Для улучшения сходимости введем так называемый параметр «сверхрелаксации» :


(4.18)

Метод, использующий эту схему, назвали методом SOR (successive overrelaxation).

Можно доказать следующие теоремы:

Метод сходится только для 0 <  < 2, если 0 <  < 1, то говорят о недостаточно быстрой релаксации

При определенных математических ограничениях, которым удовлетворяют матрицы, получающиеся в методах конечных разностей только при 1 <  < 2 этот метод сходится быстрее метода Гаусса-Зейделя.

Если ­Jacobi спектральный радиус итерационной схемы Якоби, квадрат его – спектральный радиус метода Гаусса-Зейделя), то оптимальное значение  имеет вид:


(4.19)

Спектральный радиус при этом равен





(4.20)

Если использовать выражение для радиуса Якоби из формулы (4.11), то получим:


(
4.21)

(
4.22)

Для достижения точности 10-p необходимо следующее число итераций:





(4.23)

Отсюда следует, что метод SOR для достижения точности 10-p требует количества итераций, пропорционального J, а не J2 .

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



№2

Диаграммы классов


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

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

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

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

  • Концептуальную модель, на основе которой разработчик детализирует опреде­ления классов


Когда следует создавать диаграммы классов


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

Что такое диаграммы классов



Диаграмма классов (design class diagram) иллюстрирует спецификации программных классов и интерфейсов (например, интерфейсов Java) в приложении. Обычно на та­кую диаграмму выносится следующая информация.

• Классы, ассоциации и атрибуты

• Интерфейсы со своими операциями и константами

• Методы

• Информация о типах атрибутов

• Способы навигации

• Зависимости


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

Как построить диаграмму классов


  1. Для построения диаграммы классов используется следующая стратегия.

  2. Определите все классы, задействованные в программном решении. Для этого проанализируйте диаграммы взаимодействий.

  3. Отобразите их на диаграмме классов.

  4. Перенесите на диаграмму атрибуты соответствующих понятий из концептуаль­ной модели.

  5. Добавьте имена методов на основе анализа диаграмм взаимодействия.

  6. Добавьте информацию о типах атрибутов и методов.

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

  8. Добавьте стрелки, определяющие направление навигации для ассоциаций.

  9. Добавьте линии зависимостей, определяющие другие способы обеспечения ви­димости, отличные от видимости посредством атрибутов.


Концептуальная модель и диаграммы классов


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

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


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

POST

Sale

ProductCatalog

ProductSpecification

Store

SalesLineItem

Payment





Затем необходимо нанести эти классы на диаграмму и добавить атрибуты, опреде­ленные из концептуальной модели.

Ниже представлены программные классы для системы розничной торговли.

POST

ProductCatalog


quantity

ProductSpecification


Description

Price

UPC







Store


Address

name

Sale


Date

IsComplete

time

SalesLineItem


quantity









Payment


amount







Заметим, что многие понятия концептуальной модели, такие как Cashier, Manager и Item, на диаграмме отсутствуют. Дело в том, что в рассматриваемом цикле разработки цикле нет необходимости разрабатывать их программное представление. Однако в последующих циклах, при появлении новых требований и разработке новых прецедентов они будут внесены на диаграмму.
^

Добавление имен методов



Методы каждого класса можно определить путем анализа диаграмм взаимодейст­вия (а именно — диаграмм сотрудничества). Например, если сообщение makeLineItem передается экземпляру класса Sale, то в классе Sale должен быть определен метод makeLineItem.

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

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

Выбор имен методов

При выборе имен методов необходимо руководствоваться следующими соображе­ниями.

• Интерпретировать сообщение create

• Описывать методы доступа

• Интерпретировать сообщения мультиобъектам

• Использовать синтаксис языка программирования

Сообщение create на языке UML представляет собой абстрактную форму инициа­лизации. При переходе к реализации системы на объектно-ориентированном языке программирования процесс передачи сообщения необходимо выразить средствами языка программирования с использованием его идиом дляи инициализации, В языке C++, Java или Smalltalk не существует ре­ального метода create. Например, на языке C++ или Java память выделяется с помощью оператора new, после которого следует имя конструктора.

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

Имена методов: методы доступа

Методы доступа (accessing methods) — это методы получения или установки значе­ний атрибутов. Для каждого атрибута принято создавать свои методы получения и ус­тановки значений, а сами атрибуты объявлять в закрытой области доступа (для обес­печения инкапсуляции). Эти методы обычно не отображаются на диаграмме классов, чтобы не загромождать ее лишней информацией, поскольку при наличии N атрибутов у класса появляется 2N стандартных метода. Например, метод price (или getPrice) класса ProductSpecification не показан на диаграмме классов, поскольку это простой метод доступа.

Сообщения мультиобъекту интерпретируются как сообщение контейнеру или на­бору объектов.

Например, следующее сообщение find мультиобъекту можно интерпретировать как сообщение объекту-контейнеру, такому как хэш-таблицa (hash-table) в Java, ассоциативный массив (map) в C++ или словарь (dictionary) в Smalltalk.

Таким образом, метод find не является частью класса ProductSpecification, а при­надлежит хэш-таблице или словарю определения класса. Поэтому некорректно добав­лять метод find в спецификацию класса ProductSpecification.

Классы - контейнеры (такие как Java.util.Vector и Java.util.Hash-table) — это пре­допределенная библиотека классов, которые не отображаются на диаграмме классов, поскольку они лишь загромождают диаграмму и не несут новой информации.

В некоторых языках, таких как Smalltalk, синтаксическая форма описания ме­тода отличается от базового формата UML вида имяМетода (списокПараметров). На диаграммах классов рекомендуется использовать базовый формат языка UML, даже если планируется реализовывать систему на языке с другим синтаксисом. Переход к синтаксису конкретного языка целесообразно выполнять на этапе ге­нерации кода, а не в процессе создания диаграмм классов. Однако UML допуска­ет применение различных синтаксисов для спецификации методов, в том числе синтаксис языка Smalltalk.

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

Диаграмма классов создается для пользователей.

• Если генерация кода будет выполняться автоматически с использованием CASE-средств, то на диаграмме классов необходимо отобразить полную и исчерпываю­щую информацию

• Если диаграмма классов создается для программистов, то избыточные детали мо­гут загромождать диаграмму

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

Добавление ассоциаций и информации о навигации

Каждый конец линии ассоциации называется ролью (role). На диаграмме классов роль может отмечаться стрелкой (стрелкой навигации), указывающей направление связи. Информация о навигации (navigability) — это свойство роли, указывающее воз­можное направление передачи информации от объекта-источника к целевому классу. Информация о навигации связана с видимостью объектов, обычно — с видимостью, обеспечиваемой посредством атрибутов.

Линия ассоциации со стрелкой навигации обычно интерпретируется как види­мость целевого класса для класса-источника, обеспечиваемая с помощью атрибутов. В процессе реализации на объектно-ориентированном языке программирования она обычно выражается в том, что один из атрибутов класса-источника является ссылкой на экземпляр целевого класса. В частности, один из атрибутов класса POST должен яв­ляться ссылкой на экземпляр класса Sale. Большинство (если не все) ассоциаций на диаграммах классов должны быть снабжены необходимыми стрелками навигации.

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

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

• Объект и отправляет сообщение объекту В

• Объект А создает экземпляр объекта В

• Объект А должен поддерживать связь с объектом В

Например, объект Store должен быть связан с создаваемыми им экземплярами объектов POST и ProductCatalog, причем эта связь должна быть направлена от объекта Store. Целесооб­разно также установить связь объекта ProductCatalog с создаваемым им набором объ­ектов ProductSpecifi cation. На самом деле практически всегда направление связи со­ответствует направлению от объекта-создателя к создаваемым им объектам.

На диаграмме классов такие связи представляются в виде ассоциаций,

Пользуясь приведенными выше критериями для определения ассоциаций и на­правления связей на основе анализа всех диаграмм сотрудничества, для приложения розничной торговли можно построить диаграмму классов, представленную на рисунке ниже. Заметим, что эти ассоциации не совпадают с набором ассоциаций, сгенерирован­ным для диаграммы классов на основе концептуальной модели. Например, в концеп­туальной модели между классами POST и ProductCatalog отсутствует ассоциация «входит в», поскольку на этапе создания концептуальной модели эта взаимосвязь не казалась важной. Однако в процессе создания диаграмм взаимодействия было решено, что программный объект POST должен быть связан с программным объектом ProductCatalog с целью нахождения спецификации Product Specification.
^

Добавление зависимостей


В языке UML существует Обозначение для отношения зависимости (dependency re­lationship), указывающего, что один элемент (любого типа, включая классы, прецеден­ты и т.д.) знает о другом элементе. Такое отношение отображается пунктирной лини­ей со стрелкой. На диаграмме классов отношение зависимости отображает видимость между классами, отличную от обеспечиваемой посредством атрибутов, т.е. глобаль­ную, локальную видимость или видимость, обеспечиваемую с помощью параметров. Видимость, обеспечиваемая посредством атрибутов, отображается сплошной линией ассоциации со стрелкой, которая указывает направление связи.

Например, программный объект POST получает возвращаемый объект типа ProductSpecification из сообщения, отправляемого им объекту ProductCatalog. Таким образом, для объекта POST обеспечивается кратковременная локальная видимость объ­екта ProductSpecification. Объект Sale получает ProductSpecification в качестве пара­метра метода makeLine Item (видимость, обеспечиваемая посредством параметров). Та­кие способы обеспечения видимости отображаются пунктирными линиями со стрелками, определяющими отношение зависимости.

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


Содержит


Store


Address:Address

Name :Text


AddSale()
Использует 1..*


ProductCatalog


Specification()


ProductSpecification


Description: Text

Price: Quantity

Upc: UPC
1 1 1







1




1

Содержит Выполняет поиск Содержит 1

1 1..* *

  1. 1

    Sale




    Date: Date

    IsComplete: Boolean

    Time: Time


    BecomeComplete()

    MakeLineItem()

    MakePayment()

    Total()

    SalesLineItem


    Quantity:Integer

    Subtotal()



POST


EndSale()

EnterItem()

MakePayment()

Обрабатывает



1

Payment


Amount:

Quantity






Регистрирует завершенные




1 1

Оплачивается


Диаграмма классов для информационной системы розничной торговли.



Похожие:

Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconСборник задач по физике для 10-11 классов общеобразовательных учреждений
Мастерская учителя. Элективный курс «Методы решения физических задач» 10-11 класс
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconСамонаблюдение Самооценка Социально-психологические методы Беседа интервью
Метод контрольных близнецов Метод близнецовой пары Метод контрольного близнеца Метод разлученных монозиготных близнецов Дневниковый...
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconФормы и методы предъявления задач на уроках физике на материале изучения темы "Изменение агрегатных состояний вещества"
Методики обучения физике рассматривают возможность решения задач на уроках. При этом выделяют их различные типы: комбинированный,...
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconЛекции по методам экстремальных задач. М.: Мгу, 1974
Васильев Ф. П. Численные методы решения экстремальных задач. – М.: Наука, 1980,1986,1988
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconКонспект занятия по познавательному развитию в подготовительной группе по теме: "Глазки, уши и носы быть здоровыми должны"
Развивать умение самостоятельно следить за своим здоровьем и использовать различные гимнастики, слушать музыку для релаксации
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconЭлементы комбинаторики
Математики, в котором изучаются методы решения комбинаторных задач, называется комбинаторика
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconРешение систем линейных уравнений
Имеется три основных способа решения систем линейных уравнений. Первым является метод Гаусса последовательного исключения переменных....
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconБилет № Назовите 3 аспекта влияния грозовых разрядов на подземные кабельные линии передачи. Охарактеризуйте метод рационального заземления рэс по представленному рисунку поясните эффект экранирования. Билет №
Охарактеризуйте метод анализа дипольных антенн, который базируется на представлении антенн эквивалентными схемами Тевенина
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconЗадача и примеры численных методов ее решения
Численный методы решения задачи Коши для обыкновенных дифференциальных уравнений
Билет №17 №1 Метод релаксации. Методы Якоби и Гаусса-Зейделя. Методы релаксации для решения граничных задач iconКонспект занятия Тема: Путешествие в Город Плавной речи
Оборудование: настенное зеркало, карточки со словами, фразами, массажный шарик, музыкальная композиция для релаксации, карточки артикуляции...
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами