ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 296
Скачиваний: 6
§ 2. Прямые методы |
15» |
ходимых для получения образа Фурье от заданной в N точках вещественной сеточной функции, определяется следующим обра зом.
Синус-преобразование:
ІВС = 1, |
5 # log2 N - 8N + |
6, |
N > 4 . |
||
Косинус-преобразование: |
|
|
|
|
|
ІВС = 2, |
5N log2 N — 8N + 12, |
N > |
4. |
||
Разложение в ряд: |
|
|
|
|
|
|
ІВС = 3 |
или 4 |
|
|
|
2,5N log2 N - 3,5N + |
21og2 N + |
5, |
N > |
8. |
|
Однако в последующих оценках с достаточной точностью' можно ограничиться первыми двумя членами приведенных выра жений.
Сравним число операций для периодических граничных усло вий с аналогичной характеристикой обычного быстрого преоб разования Фурье (см. [12]). Взятая из этой работы оценка дает 2,5N log2 N — 1,25# арифметических операций для ^-точечной вещественной сеточной функции и показывает, что подпрограмма FOUR67 может оказаться значительным шагом вперед по сравне нию с обычным алгоритмом для преобразования Фурье веще ственной сеточной функции. Однако на практике это преиму щество может быть утрачено ввиду крайней сложности алго ритма.
Проведенное недавно усовершенствование метода быстрого преобразования Фурье, как сообщил автору Кули, показало, что синус- и косинус-преобразования требуют не больше времени, чем разложение в полный ряд. В этом случае оценки числа опе раций и времени счета, данные ниже для программы решения уравнения Пуассона с периодическими граничными условиями, справедливы и для произвольных граничных условий.
При использовании CDG6600 время, необходимое для разло
жения |
в ряд |
Фурье |
по |
подпрограмме FOUR67, определяется |
(с точностью до 5%) |
выражением (2N log2 N + 500) мкс, а факти |
|||
ческое |
время |
разложения |
по 1024 точкам составило 0,021 с. |
|
Для достижения такой скорости пришлось наиболее важные части программы программировать в машинных кодах (на авто коде COMPASS). Вариант подпрограммы, составленный целиком на Фортране, работал в 5,7 раза медленнее и потребовал 0,125 с для того же самого расчета.
В табл. 1 приведено машинное время, необходимое для разло жения в ряд Фурье (ІВС = 3) при различных количествах задан ных точек, а в табл. 2 — машинное время для 1024 точек при различных типах допустимых граничных условий.
154 |
Гл. 4. Методы расчета потенциала |
Таблица 1
Машинное время (в секундах), необходимое для разложения в ряд Фурье ( І В С = Ъ ) с помощью подпрограммы FOUR67 при различном числе узловых точек
|
|
CDC 6600 |
IBM Фортран IV а |
||
« |
COMPASS |
Фортран |
360/67 |
Ошибка |
|
|
|||||
32 |
7,57-10-4 |
__ |
3,64-Ю -з |
2,9-10-8 |
|
64 |
1,32 |
-10-з |
6 ,0 0 -Ю-з |
7,46-Ю-з |
3,6-10-8 |
128 |
2,42 |
-10-3* |
1,20-10-2 |
1,58-10-2 |
3,4-10-8 |
256 |
4,90-Ю -з |
2,40-10-2 |
3,40-10-2 |
5,8-10-в |
|
516 |
1,01-10-2 |
5,20-10-2 |
7,44-10-2 |
6,2-10-6 |
|
1024 |
2,15-10-2 |
1,06-Ю -і |
1,61-Ю -і |
7,4-10-6 |
|
° Использован второй вариант (уровень Н) компилятора для модели 67-1.
Таблица 2
Машинное время (в секундах), необходимое для разложения в ряд Фурье и фурье-синтеза
по 1024 узловым |
точкам при применении подпрограммы |
|
FOUR67 и различных граничных условиях |
||
ІБС |
6600 а |
360/67 6 |
1 |
0,170 |
0,281 |
2 |
0,170 |
0,281 |
3 |
0,106 |
0,161 |
4 |
— |
0,166 |
° CDC Фортран IV.
6 Программа на Фортране IV; второй вариант (уровень Н) компиля тора для модели 67-1.
3. Метод Хокни (FACR)
Прямой метод фурье-анализа с применением циклической редукции (FACR) основан на разложении Фурье по одной коорди нате (например, по координате х), что позволяет затем решать гармонические уравнения по другой координате, пользуясь циклической редукцией. Если граничные условия достаточно просты, как, например, в случаях, допускаемых подпрограммой
§ 2. Прямые методы |
155 |
POTI, то синусы и косинусы являются собственными функциями рассматриваемого оператора и гармонические уравнения распа даются. При этом гармонические уравнения могут быть решены раздельно и достаточно быстро. В результате алгоритм принимает следующий вид: фурье-преобразование заданного распределения зарядов для получения гармонических составляющих заряда; решение гармонических уравнений для определения гармони ческих составляющих потенциала по гармоническим составляю щим заряда; после этого искомый потенциал определяется обрат ным преобразованием Фурье.
В случае простых граничных условий по у (аналогичных условиям по х) можно было бы выполнить фурье-преобразование и по координате у и опять-таки получить распадающиеся урав нения для гармоник. Тем не менее мы предпочли ограничиться фурье-преобразованием в одном измерении по двум причинам. Во-первых, установлено, что при двойном преобразовании Фурье число арифметических операций возрастает примерно на 50%. Во-вторых, если не проводить фурье-преобразование по второй координате, можно решать более общие задачи. Например, если ограничиться фурье-преобразованием по координате z или Ѳ, то методом FACR можно решить уравнение Пуассона в коорди натах (г, 2) или (г, Ѳ) соответственно. Мы не будем, однако, углуб ляться здесь в эту тему. Уравнения Пуассона в этих координатах имеют вид
<92 ф |
. д 2 ф |
1 |
З ф |
dz2 |
dr2 |
г |
дг |
3 2ф |
3 2 ф |
|
|
Ж |
+ Г2 дг2 |
|
|
— 4яр(г, Z),
( 12)
— 4яг2р(г, Ѳ).
При решении разностных уравнений по методу FAGR можно еще более уменьшить количество арифметических операций, использовав циклическое свойство разностных уравнений. Это свойство дает возможность исключить из рассмотрения все нечет ные строки сетки. Описанный процесс, который мы называем нечетно-четной редукцией, образует систему уравнений для чет ных строк сетки, более сложную, чем исходная. Тем не менее уравнения на четных строках сохраняют ту же симметрию, что и исходные уравнения, и допускают описанный выше метод реше ния с помощью преобразования Фурье. После того как найдено решение на четных строках, на нечетных строках решение можно получить из исходных уравнений для этих строк. Причем нечет ные уравнения можно решать независимо, поскольку решение на промежуточных четных строках уже найдено.
Для упрощения математического описания метода допустим,
что сетка квадратная (H X = HY) и что |
по координате х нало |
жены периодические граничные условия, |
а на границе по коорди- |
156 Гл. 4. Методы расчета потенциала
нате у потенциал принимает заданные значения. Исходную раз ностную систему уравнений можно записать в виде
фг_! + Ифг + фі+1 = — AnptHX2 = qt, 0 < t < N Y , |
(13) |
где векторы ф( и qj — потенциал и свободный член для t-то ряда
а) Исходные |
6) После нечетно- |
в) После преобразования |
уравнения |
четной редукции |
Фурье |
г) После циклической |
д)Решение на нечетных |
редукции и обратного |
рядах |
преобразования Фурье |
|
Ф и г . 4. Различные стадии алгоритма FACR.
Точками показан шаблон разностного оператора на каждой стадии. Четные ряды узлов сетки изображены сплошными линиями, а нечетные — пунктирными.
узлов сетки
|
Фо. t |
Qo. |
t |
|
фг |
4>i. і |
Qi, |
t |
(14) |
q« |
|
|
||
|
Ф іѵх_і,г/ |
\ Q n |
x - i , t., |
|
Матрица А определяет пятиточечныи разностный оператор
/ ~ 4 |
1 |
0 . |
|
0 |
1\ |
1 |
- 4 |
1 |
|
|
0 |
0 |
1 |
|
|
|
(15) |
А |
|
|
|
|
|
• |
|
|
1 |
|
0 |
|
|
|
|
||
0 |
|
1 |
- 4 |
|
1 |
V 1 |
0 |
0 |
1 |
|
- V |
