일반 미분방정식의 수치적 방법

Numerical methods for ordinary differential equations
미분방정식 = , (0)= 1. y 청색: 오일러 방법, 녹색: 중간점 방법, 빨강: 정확한 솔루션, = {\ y 단계 크기는 =.0 입니다
= 에 대한 동일한 그림 h → 0 {\ h0} 으로 오일러법보다 더 빠르게 수렴된다

일반 미분방정식에 대한 수치적 방법일반 미분방정식(oDE)의 해법에 대한 수치적 근사를 찾는 데 사용되는 방법이다. 이 용어는 통합 계산을 지칭할 수도 있지만, 이들의 용어는 "수리적 통합"이라고도 한다.

많은 미분 방정식은 기호 연산("분석")을 사용하여 해결할 수 없다. 그러나 엔지니어링과 같이 실용적 목적을 위해서는 종종 솔루션에 대한 수치적 근사치가 충분하다. 여기서 연구한 알고리즘은 그러한 근사치를 계산하는 데 사용될 수 있다. 다른 방법은 미적분학의 기술을 사용하여 용액의 연속적인 확장을 얻는 것이다.

보통의 미분 방정식은 물리학, 화학, 생물학, 경제학을 포함한 많은 과학 분야에서 발생한다.[1] 또한, 수치 부분 미분 방정식의 일부 방법은 부분 미분 방정식을 일반적인 미분 방정식으로 변환하며, 이는 반드시 해결되어야 한다.

문제

1차 미분 방정식은 형식의 초기값 문제(IVP)이다.[2]

(1)

where is a function , and the initial condition is a given vector. 1차분석y의 첫 번째 파생상품만 방정식에 나타나고 상위 파생상품은 없다는 것을 의미한다.

고차방정식에 대한 일반성을 상실하지 않는 한, 고차방정식을 1차방정식으로 제한하는데, 그 이유는 고차방정식은 추가 변수를 도입함으로써 1차방정식의 더 큰 시스템으로 변환될 수 있기 때문이다. 예를 들어, 2차 방정식 y= = -y는 두 개의 1차 방정식으로 다시 쓸 수 있다: y= z, z= -y.

이 절에서는 IVP에 대한 수치적 방법을 설명하고 경계문제(BVP)에는 다른 도구 세트가 필요하다고 언급한다. BVP에서 한 개 이상의 지점에서 솔루션 y의 값 또는 구성요소를 정의한다. 이 때문에 BVP를 풀기 위해서는 다른 방법을 사용할 필요가 있다. 예를 들어 사격법(및 그 변형법)이나 유한차이,[3] 갤러킨법,[4] 콜러레이션법 등과 같은 범지구적 방법이 해당 등급의 문제에 적합하다.

피카르-린델뢰프 정리f립스키츠-연속이라면 독특한 해결책이 있다고 명시하고 있다.

방법들

1차 IVP를 풀기 위한 수치적 방법은 종종 선형 다단계 방법 또는 런지-쿠타 방법[5]두 가지 큰 범주 중 하나로 분류된다. 방법을 명시적인 방법과 암묵적인 방법으로 나누면 추가적인 분열이 실현될 수 있다. For example, implicit linear multistep methods include Adams-Moulton methods, and backward differentiation methods (BDF), whereas implicit Runge–Kutta methods[6] include diagonally implicit Runge–Kutta (DIRK),[7][8] singly diagonally implicit Runge–Kutta (SDIRK),[9] and Gauss–Radau[10] (based on Gaussian quadrature[11]) numerical methods. 선형 다단계 제품군의 명시적 예로는 아담스-바시포스 방법을 들 수 있으며, 대각선 푸에르토 테이블라우가 낮은 모든 런지-쿠타 방법이 명시적이다. 느슨한 경험 법칙은 뻣뻣한 미분방정식이 암묵적인 계략의 사용을 필요로 하는 반면, 비관적인 문제는 명시적인 계략으로 더 효율적으로 해결될 수 있다는 것을 지시한다.

이른바 일반 선형법(GLM)은 위의 두 가지 큰 등급의 방법을 일반화한 것이다.[12]

오일러법

곡선의 어느 지점에서나 곡선에 접하는 선을 따라 짧은 거리를 이동하면 곡선에서 가까운 점의 근사치를 찾을 수 있다.

미분 방정식(1)부터 파생 Y difference를 유한차 근사치로 대체한다.

(2)

다시 배열하면 다음과 같은 공식이 나온다.

(1)을 사용하면 다음과 같은 이점을 얻을 수 있다.

(3)

이 공식은 보통 다음과 같은 방법으로 적용된다. 스텝 사이즈 h를 선택하고, 시퀀스 = + = t + h,.. . . . . . . . . 0}+ . 를 기준으로 정확한 y( ) y의 수치 추정치 (3)에 의해 동기 부여된 다음 반복적 방법으로 이러한 추정치를 계산한다.

(4)

이것은 오일러 방법(또는 아래 설명해야 할 후방 오일러 방법과 대조적으로 전방 오일러 방법)이다. 이 방법은 1768년 그것을 설명한 레온하르트 오일러의 이름을 따서 명명되었다.

오일러 방법은 명시적 방법의 예다. 이는 새로운 가치 yn+1 yn 같이 이미 알려진 것들의 관점에서 정의된다는 것을 의미한다.

백워드 오일러법

만약, (2) 대신에, 우리는 근사치를 사용한다.

(5)

우리는 후진 오일러 방법을 얻는다:

(6)

후진 오일러 방법은 암묵적인 방법인데, 우리가 방정식을 풀어야 yn+1 찾을 수 있다는 뜻이다. 이를 달성하기 위해 고정점 반복이나 뉴턴-랩슨 방법을 (일부 수정) 사용하는 경우가 많다.

명시적 방법보다 이 방정식을 푸는 데 더 많은 시간이 소요된다. 이 비용은 사용할 방법을 선택할 때 고려해야 한다. (6)와 같은 암묵적 방법의 장점은 경직된 방정식을 푸는 데 있어서 대개 더 안정적이기 때문에 더 큰 스텝 사이즈 h를 사용할 수 있다는 것이다.

1차 지수 통합 방법

기하급수적인 통합업체들은 최근에 많은 발전을 경험한 대규모 통합업체를 설명한다.[13] 그들은 적어도 1960년대로 거슬러 올라간다.

(1) 대신에, 우리는 미분 방정식이 형태 중 하나라고 가정한다.

(7)

또는A 비선형 용어 을(를) 생성하기 위해 배경 상태에 대해 국소적으로 선형화되었다

지수 통합자는 (7)에 e A e를 곱한 후 시간 간격 + 1= + t}+를 정확히 통합하여 구성된다

이 적분 방정식은 정확하지만 적분을 정의하지는 않는다.

1차 지수 통합자는 다음 전체 간격에 걸쳐 ( y( n+ {\ {\}+\tau )}을(를) 일정하게 유지함으로써 실현할 수 있다.

(8)

일반화

오일러 방법은 종종 충분히 정확하지 않다. 좀 더 정밀한 용어로, 순서 1만 가지고 있다(순서의 개념은 아래에서 설명한다). 이것은 수학자들이 고차적인 방법을 찾도록 만들었다.

한 가지 가능성은 이전에 계산된 값 yn 사용하여 yn+1 결정할 뿐만 아니라 솔루션이 더 많은 과거 값에 의존하도록 하는 것이다. 이것은 이른바 다단계 방법을 산출한다. 아마도 가장 간단한 방법은 두 번째 순서인 비약적인 방법이고 (거의 말로) 두 개의 시간 값에 의존한다.

거의 모든 실용적인 다단계 방법은 형태를 갖는 선형 다단계 방법의 패밀리에 속한다.

또 다른 가능성은[ + 간격에 더 많은 포인트를 사용하는 것이다 이것은 칼 룬게마틴 쿠타의 이름을 딴 룬게-쿠타 방법의 가족으로 이어진다. 그들의 4차 방식 중 하나는 특히 인기가 있다.

고급 기능

ODE를 해결하기 위해 이러한 방법들 중 하나를 잘 구현하는 것은 타임 스텝 공식보다 더 많은 것을 수반한다.

항상 같은 스텝 사이즈를 사용하는 것은 비효율적인 경우가 많기 때문에, 스텝 사이즈의 가변적인 방법이 개발되었다. 일반적으로 단계 크기는 단계당 (로컬) 오류가 일부 허용오차 수준 이하가 되도록 선택된다. 즉, 방법은 오류 표시기, 즉 로컬 오류의 추정치도 계산해야 한다.

이 아이디어의 확장자는 서로 다른 순서의 방법들 사이에서 동적으로 선택하는 것이다(이를 가변 순서 방법이라고 한다). Bulirsch-Stoer 알고리즘과 [14]같은 리처드슨 외삽에 기초한 방법들은 종종 서로 다른 주문의 다양한 방법들을 구성하기 위해 사용된다.[15][16]

기타 바람직한 특징은 다음과 같다.

  • 밀도 출력: 전체0 통합 간격에 대한 값싼 수치 근사치 및 t, t12, t, ... 지점에서만 사용할 수 있는 것은 아니다.
  • 이벤트 위치: 특정 기능이 소멸되는 시간 찾기. 이것은 일반적으로 뿌리 찾기 알고리즘을 사용해야 한다.
  • 병렬 컴퓨팅 지원
  • 시간 가역성, 시간 가역성과 관련하여 통합을 위해 사용할 경우

대체 방법

많은 방법들이 여기서 논의된 틀 안에 들어가지 않는다. 대체 방법의 일부 클래스는 다음과 같다.

  • 함수 f뿐만 아니라 파생 모델도 사용하는 다변형 방법. 이 세분류는 Hermite-Obreschkoff 방법 Fehlberg 방법뿐만 아니라 솔루션 y테일러 시리즈의 계수를 반복적으로 계산하는 Parker-Sochaki 방법[17] 또는 Bychkov-Sherbakov 방법과 같은 방법을 포함한다.
  • 번째 순서 ODE에 대한 방법. 우리는 모든 고차 ODE가 (1) 형태의 1차 주문 ODE로 변환될 수 있다고 말했다. 이것이 확실히 사실이지만, 그것이 진행하기에 가장 좋은 방법은 아닐 수도 있다. 특히 니스트룀 방법은 2차 방정식과 직접 작용한다.
  • 기하학적 통합 방법[18][19] 특히 특수 등급의 ODE를 위해 설계된다(예를 들어, 해밀턴 방정식의 해답을 위한 복합적 통합자). 그들은 숫자 솔루션이 이러한 등급의 기초적인 구조나 기하학을 존중하도록 주의한다.
  • 정량화된 상태 시스템 방법은 상태 정량화 아이디어에 기초한 ODE 통합 방법의 한 계열이다. 그것들은 빈번한 불연속성을 가진 희박한 시스템을 시뮬레이션할 때 효율적이다.

병렬 처리 방법

슈퍼컴퓨터병렬 컴퓨팅이 필요한 어플리케이션의 경우, 수치적 방법에 의해 제공되는 동시성의 정도는 관련성이 있다. 엑사스케일 컴퓨팅 시스템의 도전을 고려하여, 동시성을 시간적 방향으로 제공할 수 있는 초기 가치 문제에 대한 수치적 방법이 연구되고 있다.[20] 파라알은 이와 같은 병렬적 시간 통합 방법의 비교적 잘 알려진 예지만, 초기 아이디어는 1960년대로 거슬러 올라간다.[21] 엑사스케일 컴퓨팅의 등장에서, 시간 병렬 통합 방법은 다시 증가된 관심을 받는다. 지수 통합자를 위한 알고리즘은 예를 들어 병렬 통합자를 쉽고 효율적으로 구현할 수 있는 표준화된 Batched BLAS 기능을 활용할 수 있다.[22]

분석

수치해석은 수치적 방법의 설계일 뿐만 아니라 그들의 분석이기도 하다. 이 분석의 세 가지 중심 개념은 다음과 같다.

  • 수렴: 방법이 솔루션에 근접한지 여부,
  • 순서: 용액에 근접한 정도 및
  • 안정성: 오류가 감쇠되는지 여부.[23]

수렴

단계 h가 0으로 가면서 수치용액이 정확한 용액에 접근하면 수치방법이 수렴된다고 한다. 더 정확히 말하면, 우리는 Lipschitz 함수 f를 가진 모든 ODE(1)와 * t > 0을 필요로 한다.

위에서 언급한 모든 방법들이 수렴된다.

일관성 및 순서

숫자 방법이 다음과 같다고 가정합시다.

메소드의 로컬(truncation) 오류는 메소드의 한 단계에 의해 커밋된 오류다. 즉, 이전 단계에서 오류가 발생하지 않았다고 가정하여 방법에 의해 주어진 결과와 정확한 해결책의 차이점이다.

이 방법은 다음과 같은 경우에 일관된다고 한다.

다음 경우 메소드에 주문 이(가) 있음

따라서 방법이 0보다 큰 주문을 갖는 경우 일관성이 있다. 위에서 소개한 (전진) 오일러 방식(4)과 후진 오일러 방식(6)은 모두 순서 1이 있으므로 일관성이 있다. 실제로 사용되는 대부분의 방법은 더 높은 질서에 도달한다. 일관성은 수렴을[citation needed] 위해 필요한 조건이지만 충분하지는 않다. 어떤 방법이 수렴되려면 일관성이 있어야 하고 안정성이 있어야 한다.

A related concept is the global (truncation) error, the error sustained in all the steps one needs to reach a fixed time . Explicitly, the global error at time is where . The glob al error th order 1-step 는 O( ) 이다 특히 이러한 방법은 수렴된다. 이 진술은 다단계 방법에서 반드시 맞는 것은 아니다.

안정성 및 강성

일부 미분 방정식의 경우, 오일러 방법, 명시적 런지-쿠타 방법 또는 다단계 방법(예: Adams-Bashforth 방법)과 같은 표준 방법의 적용은 다른 방법들이 안정적인 해결책을 산출할 수 있지만 솔루션의 불안정성을 나타낸다. 방정식에서 이러한 "어려운 행동"(필요하게 복잡할 필요는 없을 수도 있음)은 경직성이라고 설명되며, 종종 근본적인 문제에 다른 시간 척도가 존재하기 때문에 발생한다.[24] 예를 들어 충격 오실레이터와 같은 기계적 시스템에서 충돌은 일반적으로 물체의 움직임 시간보다 훨씬 작은 시간 척도로 발생한다. 이 불일치는 상태 매개변수의 곡선에서 매우 "흔들린 회전"을 만든다.

화학 운동학, 제어 이론, 고체 역학, 일기 예보, 생물학, 플라즈마 물리학, 전자공학에서 뻣뻣한 문제들이 어디에나 있다. 강성을 극복하는 한 가지 방법은 미분방정식의 개념을 미분방정식의 개념을 미분방정식의 포함으로 확장하는 것이다.[25][26]

역사

아래는 이 분야의 몇 가지 중요한 발전의 연대표다.[27][28]

2차원의 1차원 경계값 문제에 대한 수치해법

경계 값 문제(BVP)는 대개 원래 BVP를 탈바꿈하여 얻은 대략 동등한 매트릭스 문제를 해결함으로써 수적으로 해결된다.[29] BVP를 하나의 차원으로 수치적으로 해결하기 위해 가장 일반적으로 사용되는 방법을 유한차이법이라고 한다.[3] 이 방법은 점 값의 선형 조합을 이용하여 함수의 파생상품을 설명하는 유한 차이 계수를 구성한다. 예를 들어, 첫 번째 파생상품에 대한 2차 중심차이의 근사치는 다음과 같다.

두 번째 파생상품의 2차 중심차이는 다음과 같다.

이 두 공식에서 = - - 1 은(는) 디스코트된 도메인에서 인접한 x 사이의 거리다. 그런 다음 표준 매트릭스 방법으로 해결할 수 있는 선형 시스템을 구축한다. 예를 들어, 해결할 방정식은 다음과 같다고 가정합시다.

다음 단계는 문제를 확인하고 다음과 같은 선형 파생 모델 근사치를 사용하는 것이다.

그리고 선형 방정식의 결과 시스템을 해결한다. 이는 다음과 같은 방정식을 초래할 수 있다.

처음 봤을 때 이 방정식 체계는 방정식이 변수에 곱하지 않은 항을 포함하지 않는다는 사실과 연관되는 어려움을 가지고 있는 것으로 보이지만, 사실 이것은 거짓이다. i = 1과 n - 1에서 경계 값 = u )= n {\을 포함하는 용어가 있으며, 이 두 값이 알려져 있기 때문에 단순히 이 방정식으로 대체할 수 있고 그 결과 비동종 선형 시스템을 갖게 된다. 해결책

참고 항목

메모들

  1. ^ 치코네, C. (2006년). 용도가 있는 일반 미분 방정식(Vol. 34). 스프링거 사이언스 & 비즈니스 미디어.
  2. ^ 브래디(2006, 페이지 533–655)
  3. ^ a b 르베크, R. J. (2007) 일반 및 부분 미분 방정식의 유한 차이 방법: 정상 상태 및 시간에 따른 문제(Vol. 98). SIAM.
  4. ^ Slimane Adjerid and Mahboub Bacouch(2010) Galerkin 방법. 스콜라페디아, 5(10:10056).
  5. ^ 그리피스, D. F., & Higham, D. J. (2010) 일반적인 미분방정식에 대한 수치적 방법: 초기값 문제. 스프링거 사이언스 & 비즈니스 미디어.
  6. ^ Hairer, Nørsett & Wanner(1993, 페이지 204–215)
  7. ^ 알렉산더, R. (1977년) 경직된 ODE에 대한 대각선 암묵적 Runge-Kutta 방법. 수치해석에 관한 SIAM 저널, 14(6), 1006-1021.
  8. ^ 현금, J. R. (1979) 대각선 암묵적 Runge-Kutta 공식(오류 추정치 포함) IMA Journal of Applied Math, 24(3), 293-301.
  9. ^ 페라시나, L, & 스피커, M. N. (2008) 단독-직관적으로-불확실한 Runge-Kutta 방법의 강한 안정성. 응용수학, 58(11), 1675-1686.
  10. ^ 에버하트, E. (1985) Gauss-Radau 스페이싱을 사용하는 효율적인 통합자. 국제천문연맹 콜로키움(Vol. 83, 페이지 185-202)에서. 케임브리지 대학 출판부.
  11. ^ 와이스슈타인, 에릭 W. "가우스 쿼드라처" Wolfram Web Resource에서 온. https://mathworld.wolfram.com/GaussianQuadrature.html
  12. ^ 도살자, J. C. (1987년) 일반 미분방정식의 수치해석: Runge-Kutta 및 일반 선형 방법. 와일리-인터사이언스
  13. ^ Hochbruck (2010, 페이지 209–286) 2010 ( 지수 통합업체를 위한 현대적이고 광범위한 검토 논문이다.
  14. ^ Brezinski, C, & Zaglia, M. R. (2013) 외삽법: 이론과 실천. 엘시비어.
  15. ^ 먼로, J. L. (2002) 외삽법 및 Bulirsch-Stoer 알고리즘. 신체 검토 E, 65(6), 066116.
  16. ^ 키르페카르, S. (2003) Bulirsch Stoer 외삽법의 시행. UC 버클리/캘리포니아 기계공학부.
  17. ^ 누르민스키, E. A., & Bury, A. A. (2011년) 파커-소차키 방식은 그래픽 프로세서를 이용해 일반 미분방정식의 시스템을 푸는 방식이다. 수치해석 및 적용, 4(3), 223.
  18. ^ 하이레르, E, 루비히, C, & 워너, G. (2006) 기하학적 수치 통합: 일반적인 미분 방정식을 위한 구조 보존 알고리즘(Vol. 31). 스프링거 사이언스 & 비즈니스 미디어.
  19. ^ Hairer, E, Lubich, C, & Wanner, G. (2003) Störmer-Verlet 방법에 의해 설명된 기하학적 수치 통합. 액타 숫자, 12, 399-450
  20. ^ Gander, Martin J. 50 years of Time Parallel Time Integration. Contributions in Mathematical and Computational Sciences. 9 (1 ed.). Springer International Publishing. doi:10.1007/978-3-319-23321-5. ISBN 978-3-319-23321-5.
  21. ^ Nievergelt, Jürg (1964). "Parallel methods for integrating ordinary differential equations". Communications of the ACM. 7 (12): 731–733. doi:10.1145/355588.365137.
  22. ^ Herb, Konstantin; Welter, Pol (2022). "Parallel time integration using Batched BLAS (Basic Linear Algebra Subprograms) routines". Computer Physics Communications. 270: 108181. arXiv:2108.07126. doi:10.1016/j.cpc.2021.108181.
  23. ^ Higham, N. J. (2002). Accuracy and stability of numerical algorithms (Vol. 80). SIAM.
  24. ^ Miranker, A. (2001). Numerical Methods for Stiff Equations and Singular Perturbation Problems: and singular perturbation problems (Vol. 5). Springer Science & Business Media.
  25. ^ Markus Kunze and Tassilo Kupper (2001). "Non-smooth Dynamical Systems: An Overview". In Bernold Fiedler (ed.). Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems. Springer Science & Business Media. p. 431. ISBN 978-3-540-41290-8.CS1 maint: uses authors parameter (link)
  26. ^ Thao Dang (2011). "Model-Based Testing of Hybrid Systems". In Justyna Zander, Ina Schieferdecker and Pieter J. Mosterman (ed.). Model-Based Testing for Embedded Systems. CRC Press. p. 411. ISBN 978-1-4398-1845-9.
  27. ^ Brezinski, C., & Wuytack, L. (2012). Numerical analysis: Historical developments in the 20th century. Elsevier.
  28. ^ Butcher, J. C. (1996). A history of Runge-Kutta methods. Applied numerical mathematics, 20(3), 247-260.
  29. ^ Ascher, U. M., Mattheij, R. M., & Russell, R. D. (1995). Numerical solution of boundary value problems for ordinary differential equations. Society for Industrial and Applied Mathematics.

References

  • Bradie, Brian (2006). A Friendly Introduction to Numerical Analysis. Upper Saddle River, New Jersey: Pearson Prentice Hall. ISBN 978-0-13-013054-9.
  • J. C. Butcher, Numerical methods for ordinary differential equations, ISBN 0-471-96758-0
  • Ernst Hairer, Syvert Paul Nørsett and Gerhard Wanner, Solving ordinary differential equations I: Nonstiff problems, second edition, Springer Verlag, Berlin, 1993. ISBN 3-540-56670-8.
  • Ernst Hairer and Gerhard Wanner, Solving ordinary differential equations II: Stiff and differential-algebraic problems, second edition, Springer Verlag, Berlin, 1996. ISBN3-540-60452-9.
    (This two-volume monograph systematically covers all aspects of the field.)
  • Hochbruck, Marlis; Ostermann, Alexander (May 2010). "Exponential integrators". Acta Numerica. 19: 209–286. Bibcode:2010AcNum..19..209H. CiteSeerX 10.1.1.187.6794. doi:10.1017/S0962492910000048.
  • Arieh Iserles, A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, 1996. ISBN0-521-55376-8 (hardback), ISBN0-521-55655-4 (paperback).
    (Textbook, targeting advanced undergraduate and postgraduate students in mathematics, which also discusses numerical partial differential equations.)
  • John Denholm Lambert, Numerical Methods for Ordinary Differential Systems, John Wiley & Sons, Chichester, 1991. ISBN0-471-92990-5.
    (Textbook, slightly more demanding than the book by Iserles.)

External links