Gauss-Legendre-metoden

Inom numerisk analys och vetenskaplig beräkning är Gauss-Legendre-metoderna en familj av numeriska metoder för vanliga differentialekvationer . Gauss-Legendre-metoder är implicita Runge-Kutta-metoder . Mer specifikt är de samlokaliseringsmetoder baserade på punkterna i Gauss–Legendre-kvadraturen . Gauss-Legendre-metoden baserad på s poäng har ordningen 2 s .

Alla Gauss-Legendre-metoder är A-stabila .

Gauss-Legendre-metoden av ordning två är den implicita mittpunktsregeln . Dess Butcher-tablå är:

1/2	1/2
	1

Gauss-Legendre-metoden av ordning fyra har Butcher-tableau:

${\tfrac {1}{2}}-{\tfrac {1}{6}}{\sqrt {3}}$	${\tfrac {1}{4}}$	${\tfrac {1}{4}}-{\tfrac {1}{6}}{\sqrt {3}}$
${\tfrac {1}{2}}+{\tfrac {1}{6}}{\sqrt {3}}$	${\tfrac {1}{4}}+{\tfrac {1}{6}}{\sqrt {3}}$	${\tfrac {1}{4}}$
	${\tfrac {1}{2}}$	${\tfrac {1}{2}}$

Gauss-Legendre-metoden för ordning sex har Butcher-tableau:

${\tfrac {1}{2}}-{\tfrac {1}{10}}{\sqrt {15}}$	${\tfrac {5}{36}}$	${\tfrac {2}{9}}-{\tfrac {1}{15}}{\sqrt {15}}$	${\tfrac {5}{36}}-{\tfrac {1}{30}}{\sqrt {15}}$
${\tfrac {1}{2}}$	${\tfrac {5}{36}}+{\tfrac {1}{24}}{\sqrt {15}}$	${\tfrac {2}{9}}$	${\tfrac {5}{36}}-{\tfrac {1}{24}}{\sqrt {15}}$
${\tfrac {1}{2}}+{\tfrac {1}{10}}{\sqrt {15}}$	${\tfrac {5}{36}}+{\tfrac {1}{30}}{\sqrt {15}}$	${\tfrac {2}{9}}+{\tfrac {1}{15}}{\sqrt {15}}$	${\tfrac {5}{36}}$
	${\tfrac {5}{18}}$	${\tfrac {4}{9}}$	${\tfrac {5}{18}}$

Beräkningskostnaden för Gauss-Legendre-metoder av högre ordning är vanligtvis överdriven, och därför används de sällan.

Intuition

Gauss-Legendre Runge-Kutta (GLRK) metoder löser en vanlig differentialekvation ${\dot {x}}=f(x)$ med $x(0) )=x_{0}$ . Det utmärkande för GLRK är uppskattningen av $x(h)-x_{0}=\int _{0}^{h}dt \,f\circ x(t)$ med Gaussisk kvadratur .

$x(h)=x(0)+{\frac {h}{2}} \sum _{i=1}^{l}w_{i}k_{i}+O(h^{2l})$ ,

där $k_{i}=f\circ x(hc_{i})$ är de samplade hastigheterna, $w_{i}$ är kvadraturvikterna , $c_{i}={\frac {h}{2}}(1+r_{i})$ är abskissorna, och $r_ {i}$ är rötterna $P_{l}(r_{i})=0$ av Legendre-polynomet av grad $l$ . En ytterligare approximation behövs, eftersom $k_{i}$ fortfarande är omöjlig att utvärdera. För att bibehålla trunkeringsfel av ordning $O(h^{2l})$ behöver vi bara $k_{i}$ för att beställa ${\ displaystil O(h^{2l-1})}$ . Runge-Kuttas implicita definition $k_{i}=f\left(x_{0}+h\sum _{j}a_{ij} k_{j}\right)$ anropas för att åstadkomma detta. Detta är en implicit begränsning som måste lösas med en rothittande algoritm som Newtons metod . Värdena för Runge-Kutta-parametrarna $a_{ij}$ kan bestämmas från en Taylor-serieexpansion i $h$ .

Praktiskt exempel

Gauss-Legendre-metoderna är implicita, så i allmänhet kan de inte tillämpas exakt. Istället gör man en kvalificerad gissning av $k_{i}$ , och använder sedan Newtons metod för att konvergera godtyckligt nära den sanna lösningen. Nedan finns en Matlab-funktion som implementerar Gauss-Legendre-metoden i ordning fyra.

     

  
  
  
   
         
     


    




 
  
    
    
    

    
     
      

      

      0
          
          


   
    
    
         0
    
  

  
    
      
      
    
    

    
      
      
    

           
     
  
         
       
        
   
       
       
   
         
            
    
           
      
      
   
       
  
     
     
  
            
 % startpunkt  x  =  [  10,5440  ;  4,1124  ;  35,8233  ];  dt  =  0,01  ;  N  =  10000  ;  x_serie  =  [  x  ];  för  i  =  1  :  Nx  =  gauss_steg  (  x  ,  @  lorenz_dynamics  ,  dt  ,  1e-7  ,  1  ,  100  )  ;  x_serie  =  [  x_serie  x  ];  slutplot3  (  x_series  (  1  ,:),  x_series  (  2  ,  :),  x_series  (  3  ,:)  );  set  (  gca  ,  'xtick'  ,[],  'ytick'  ,[],  'ztick'  ,[]);  titel  (  'Lorenz Attractor'  );  återvända  ;  funktion  [td, j] = lorenz_dynamics  (  tillstånd  )  % returnerar en tidsderivata och en jakobisk av den tidsderivatan  x  =  tillstånd  (  1  );  y  =  tillstånd  (  2  );  z  =  tillstånd  (  3  );  sigma  =  10  ;  beta  =  8/3  ;  _  _  rho  =  28  ;  td  =  [  sigma  *  (  y  -  x  );  x  *  (  rho  -  z  )  -y  ;  _  x  *  y  -  beta  *  z  ];  j  =  [  -  sigma  ,  sigma  ,  ;  rho  -  z  ,  -1  ,  -x  ;  _  _  y  ,  x  ,  -  beta  ];  slutfunktion  x_next  =  gauss_step  ( x, dynamik, dt   ,  tröskel, dämpning, max_iterationer  )  [  d  ,  ~  ]  =  storlek  (  x  );  sq3  =  sqrt  (  3  );  om  dämpning  >  1  ||  dämpning  <=  fel  (  'dämpningen bör vara mellan 0 och 1.' )  slut  %  Använd explicita Euler-steg som initiala gissningar  [  k  ,  ~  ]  =  dynamik  (  x  );  x1_guess  =  x  +  (  1  /  2  -  sq3  /  6  )  *  dt  *  k  ;  x2_guess  =  x  +  (  1  /  2  +  sq3  /  6  )  *  dt  *  k  ;  [  k1  ,  ~  ]  =  dynamik  (  x1_guess  );  [  k2  ,  ~  ]  =  dynamik  (  x2_guess  );  a11  =  1/4  ;  _  _  a12  =  1/4  -  sq3  /  6  ;  _  _  a21  =  1/4  +  sq3  /  6  ;  _  _  a22  =  1/4  ;  _  _  fel  =  @(  k1  ,  k2  )  [  k1  -  dynamik  (  x  +  (  a11  *  k1  +  a12  *  k2  )  *  dt  );  k2  -  dynamik  (  x  +  (  a21  *  k1  +  a22  *  k2  )  *  dt  )];  er  =  fel  (  k1  ,  k2  );  iteration  =  1  ;  while  (  norm  (  er  )  >  tröskel  &&  iteration  <  max_iterations  )  fprintf  (  'Newton iteration %d: felet är %f.\n'  ,  iteration  ,  norm  (  er  )  );  iteration  =  iteration  +  1  ;  [  ~  ,  j1  ]  =  dynamik  (  x  +  (  a11  *  k1  +  a12  *  k2  )  *  dt  );  [  ~  ,  j2  ]  =  dynamik  (  x  +  (  a21  *  k1  +  a22  *  k2  )  *  dt  );  j  =  [  öga  (  d  )  -dt  *  a11  *  j1  ,  -dt  *  a12  *  j1  ;  _  _  -dt  *  a21  *  j2  ,  öga  (  d  )  -dt  *  a22  *  j2  ]  ;  _  k_nästa  =  [  k1  ;  k2  ]  -  dämpning  *  linsolve  (  j  ,  er  );  k1  =  k_nästa  (  1  :  d  );  k2  =  k_nästa  (  d  +  (  1  :  d  ));  er  =  fel  (  k1  ,  k2  );  end  if  norm  (  er  )  >  tröskelfel  (  'Newton konvergerade inte med %d iterationer.'  ,  max_iterations  )  ;  slut  x_next  =  x  +  dt  /  2  *  (  k1  +  k2  );  slutet 

Denna algoritm är förvånansvärt billig. Felet i $k_{i}$ kan falla under $10^{-12}$ i så få som 2 Newtonsteg. Det enda extraarbetet jämfört med explicita Runge-Kutta-metoder är beräkningen av Jacobian.

En integrerad bana nära Lorenz-attraktorn.

Tidssymmetriska varianter

Till priset av att lägga till en ytterligare implicit relation kan dessa metoder anpassas för att ha tidsomkastningssymmetri. I dessa metoder används den genomsnittliga positionen ${\displaystyle (x_{f}+x_{i})/2} för att beräkna$$k_{i}$ istället för att bara startpositionen $x_{i}$ i vanliga Runge-Kutta-metoder. Metoden för ordning 2 är bara en implicit mittpunktsmetod.

$k_{1}=f\left({\frac {x_{f}+x_{i}}{2}}\höger)$

$x_{f}=x_{i}+hk_{1}$

Metoden för ordning 4 med 2 steg är som följer.

$k_{1}=f\left({\frac {x_{f}+x_{i}}{2}}-{ \frac {\sqrt {3}}{6}}hk_{2}\right)$

$k_{2}=f\left ({\frac {x_{f}+x_{i}}{2}}+{\frac {\sqrt {3}}{6}}hk_{1}\right)$

$x_{f}=x_{i}+{\frac {h}{2}}(k_{1}+k_{2})$

Metoden för ordning 6 med 3 steg är som följer.

$k_{1}=f\left({\frac {x_{f}+x_{i}} {2}}-{\frac {\sqrt {15}}{15}}hk_{2}-{\frac {\sqrt {15}}{30}}hk_{3}\right)$

$k_{2}=f\left({\frac {x_{f}+x_{i}}{2}} +{\frac {\sqrt {15}}{24}}hk_{1}-{\frac {\sqrt {15}}{24}}hk_{3}\right)$

$k_{3}=f\left({\frac {x_{f}+x_{i}}{2}}+{\frac {\sqrt {15}}{30}}hk_{1}+{\frac {\sqrt {15}}{15}}hk_{2}\right)$

$x_{f}=x_{i}+{\frac {h}{18}}(5k_{1}+8k_{2}+5k_{3})$

Anteckningar

•   Iserles, Arieh (1996), A First Course in the Numerical Analysis of Differential Equations , Cambridge University Press , ISBN 978-0-521-55655-2 .