580:
852:
98:, in which the solution-function's values are specified on boundary of a domain; the problem is to compute a solution also on its interior. Relaxation methods are used to solve the linear equations resulting from a discretization of the differential equation, for example by finite differences.
308:
335:
868:
While the method converges under general conditions, it typically makes slower progress than competing methods. Nonetheless, the study of relaxation methods remains a core part of linear algebra, because the transformations of relaxation theory provide excellent
634:, the relaxation method assigns the given values of function φ to the grid points near the boundary and arbitrary values to the interior grid points, and then repeatedly performs the assignment φ := φ* on the interior points, where φ* is defined by:
640:
141:
1146:. Egon Balas (foreword) (Translated by Steven Vajda from the (1983 Paris: Dunod) French ed.). Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489.
575:{\displaystyle \varphi (x,y)={\tfrac {1}{4}}\left(\varphi (x{+}h,y)+\varphi (x,y{+}h)+\varphi (x{-}h,y)+\varphi (x,y{-}h)\,-\,h^{2}{\nabla }^{2}\varphi (x,y)\right)\,+\,{\mathcal {O}}(h^{4})\,.}
1058:(1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)".
1256:. Classics in Applied Mathematics. Vol. 30 (Reprint of the 1970 Academic Press ed.). Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. xxvi+572.
953:. Classics in Applied Mathematics. Vol. 30 (Reprint of the 1970 Academic Press ed.). Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. xxvi+572.
625:
1213:
847:{\displaystyle \varphi ^{*}(x,y)={\tfrac {1}{4}}\left(\varphi (x{+}h,y)+\varphi (x,y{+}h)+\varphi (x{-}h,y)+\varphi (x,y{-}h)\,-\,h^{2}f(x,y)\right)\,,}
1455:
303:{\displaystyle {\frac {d^{2}\varphi (x)}{{dx}^{2}}}={\frac {\varphi (x{-}h)-2\varphi (x)+\varphi (x{+}h)}{h^{2}}}\,+\,{\mathcal {O}}(h^{2})\,.}
83:
1429:
1292:
1204:
1093:
72:
1450:
1414:
1399:
1363:
1261:
1245:
1221:
1151:
1067:
1042:
958:
121:
a difficult problem by a simpler problem whose "relaxed" solution provides information about the solution of the original problem.
887:
values for the other grid points as the initial assignment. This can then also be done recursively for the coarser computation.
879:
may be used to accelerate the methods. One can first compute an approximation on a coarser grid – usually the double spacing 2
109:, it resembles repeated application of a local smoothing filter to the solution vector. These are not to be confused with
28:
1445:
921:
873:
for new methods. Indeed, the choice of preconditioner is often more important than the choice of iterative method.
110:
130:
114:
591:
915:
1422:
Advances in
Imaging and Electron Physics, Vol. 116, Numerical Field Calculation for Charged Particle Optics
135:
When φ is a smooth real-valued function on the real numbers, its second derivative can be approximated by:
95:
47:
68:
35:
106:
91:
87:
118:
1055:
1323:
1139:
1011:
1110:
1030:
76:
1425:
1410:
1395:
1359:
1288:
1257:
1241:
1217:
1147:
1063:
1038:
954:
927:
876:
61:
27:
This article is about iterative methods for solving systems of equations. For other uses, see
1313:
1201:
1102:
988:
901:
897:
82:
Relaxation methods are important especially in the solution of linear systems used to model
43:
1271:
1161:
1122:
1077:
968:
1267:
1208:
1157:
1118:
1091:
Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities".
1073:
964:
870:
64:
1439:
924:
can be applied to either of the Jacobi and Gauss–Seidel methods to speed convergence.
908:
884:
57:
54:
1280:
1306:
1186:
17:
1301:
1181:
75:
problems and also for systems of linear inequalities, such as those arising in
313:
Using this in both dimensions for a function φ of two arguments at the point (
102:
79:. They have also been developed for solving nonlinear systems of equations.
1106:
1114:
1199:
William L. Briggs, Van Emden Henson, and Steve F. McCormick (2000),
896:
In linear systems, the two main classes of relaxation methods are
860:
The method is easily generalized to other numbers of dimensions.
1279:
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007).
1320:, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
1254:
Iterative solution of nonlinear equations in several variables
995:, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
951:
Iterative solution of nonlinear equations in several variables
71:. They are also used for the solution of linear equations for
547:
275:
1062:. New York: John Wiley & Sons Inc. pp. 453–464.
630:
numerically on a two-dimensional grid with grid spacing
1168:. Editions Tec & Doc, Paris, 2008. xxx+711 pp. . ).
1287:(3rd ed.). New York: Cambridge University Press.
673:
361:
643:
594:
585:
To approximate the solution of the
Poisson equation:
338:
144:
101:
Iterative relaxation of solutions is commonly dubbed
53:
Relaxation methods were developed for solving large
1329:, Academic Press, 1971. (reprinted by Dover, 2003)
1285:Numerical Recipes: The Art of Scientific Computing
1166:Programmation mathématique: Théorie et algorithmes
1017:, Academic Press, 1971. (reprinted by Dover, 2003)
944:
942:
846:
619:
574:
302:
1238:Nonnegative Matrices in the Mathematical Sciences
1035:Nonnegative Matrices in the Mathematical Sciences
1144:Mathematical programming: Theory and algorithms
1214:Society for Industrial and Applied Mathematics
8:
1384:Numerical Analysis of Electromagnetic Fields
1307:Iterative Methods for Sparse Linear Systems
1187:Iterative Methods for Sparse Linear Systems
1390:P. Grivet, P.W. Hawkes, A.Septier (1972).
1327:Iterative Solution of Large Linear Systems
1015:Iterative Solution of Large Linear Systems
1348:Relaxation Methods in Theoretical Physics
1341:Relaxation Methods in Engineering Science
1252:Ortega, J. M.; Rheinboldt, W. C. (2000).
949:Ortega, J. M.; Rheinboldt, W. C. (2000).
918:is an improvement upon the Jacobi method.
840:
811:
806:
802:
791:
756:
733:
698:
672:
648:
642:
620:{\displaystyle {\nabla }^{2}\varphi =f\,}
616:
601:
596:
593:
568:
559:
546:
545:
544:
540:
511:
506:
499:
494:
490:
479:
444:
421:
386:
360:
337:
296:
287:
274:
273:
272:
268:
260:
244:
203:
191:
180:
172:
152:
145:
143:
1375:Numerical Techniques in Electromagnetics
1134:
1132:
105:because with certain equations, such as
1407:Electrostatic Lens Systems, 2nd edition
1007:
1005:
1003:
1001:
984:
982:
980:
978:
938:
84:elliptic partial differential equations
1177:
1175:
7:
1236:Abraham Berman, Robert J. Plemmons,
1025:
1023:
1350:. Oxford University Press, Oxford.
1343:. Oxford University Press, Oxford.
1281:"Section 18.3. Relaxation Methods"
1094:Mathematics of Operations Research
597:
507:
25:
125:Model problem of potential theory
1164:. (2008 Second ed., in French:
50:, including nonlinear systems.
1456:Relaxation (iterative methods)
911:is a simple relaxation method.
832:
820:
799:
779:
770:
750:
741:
721:
712:
692:
666:
654:
565:
552:
532:
520:
487:
467:
458:
438:
429:
409:
400:
380:
354:
342:
293:
280:
252:
238:
229:
223:
211:
197:
167:
161:
1:
883:– and use that solution with
1392:Electron Optics, 2nd edition
898:stationary iterative methods
864:Convergence and acceleration
94:. These equations describe
29:Relaxation (disambiguation)
1472:
922:Successive over-relaxation
128:
26:
1356:Classical Electrodynamics
1354:John. D. Jackson (1999).
1318:Matrix Iterative Analysis
1310:, 1st edition, PWS, 1996.
1212:(2nd ed.), Philadelphia:
1190:, 1st edition, PWS, 1996.
993:Matrix Iterative Analysis
131:Discrete Poisson equation
115:mathematical optimization
1451:Numerical linear algebra
1405:D. W. O. Heddle (2000).
90:and its generalization,
1377:. Boca Raton: CRC Pres.
1346:Southwell, R.V. (1946)
1339:Southwell, R.V. (1940)
902:Krylov subspace methods
900:, and the more general
96:boundary-value problems
1373:M.N.O. Sadiku (1992).
848:
621:
576:
304:
69:differential equations
1420:Erwin Kasper (2001).
1386:. New York: Springer.
1358:. New Jersey: Wiley.
849:
622:
577:
321:), and solving for φ(
305:
36:numerical mathematics
1202:A Multigrid Tutorial
1107:10.1287/moor.5.3.388
1056:Murty, Katta G.
641:
592:
336:
142:
73:linear least-squares
48:systems of equations
1382:P.-B. Zhou (1993).
1324:David M. Young, Jr.
1012:David M. Young, Jr.
916:Gauss–Seidel method
857:until convergence.
1424:. Academic Press.
1394:. Pergamon Press.
1207:2006-10-06 at the
1060:Linear programming
1031:Robert J. Plemmons
844:
682:
617:
572:
370:
300:
107:Laplace's equation
92:Poisson's equation
88:Laplace's equation
77:linear programming
40:relaxation methods
1446:Iterative methods
1430:978-0-12-014758-8
1294:978-0-521-88068-8
928:Multigrid methods
877:Multigrid methods
681:
369:
266:
186:
62:finite-difference
60:, which arose as
44:iterative methods
18:Relaxation method
16:(Redirected from
1463:
1387:
1378:
1369:
1314:Richard S. Varga
1298:
1275:
1225:
1197:
1191:
1179:
1170:
1169:
1136:
1127:
1126:
1088:
1082:
1081:
1052:
1046:
1029:Abraham Berman,
1027:
1018:
1009:
996:
989:Richard S. Varga
986:
973:
972:
946:
853:
851:
850:
845:
839:
835:
816:
815:
795:
760:
737:
702:
683:
674:
653:
652:
626:
624:
623:
618:
606:
605:
600:
581:
579:
578:
573:
564:
563:
551:
550:
539:
535:
516:
515:
510:
504:
503:
483:
448:
425:
390:
371:
362:
309:
307:
306:
301:
292:
291:
279:
278:
267:
265:
264:
255:
248:
207:
192:
187:
185:
184:
179:
170:
157:
156:
146:
21:
1471:
1470:
1466:
1465:
1464:
1462:
1461:
1460:
1436:
1435:
1381:
1372:
1366:
1353:
1336:
1334:Further reading
1295:
1278:
1264:
1251:
1233:
1228:
1209:Wayback Machine
1198:
1194:
1180:
1173:
1154:
1138:
1137:
1130:
1090:
1089:
1085:
1070:
1054:
1053:
1049:
1028:
1021:
1010:
999:
987:
976:
961:
948:
947:
940:
936:
893:
871:preconditioners
866:
807:
688:
684:
644:
639:
638:
595:
590:
589:
555:
505:
495:
376:
372:
334:
333:
329:), results in:
283:
256:
193:
171:
148:
147:
140:
139:
133:
127:
65:discretizations
32:
23:
22:
15:
12:
11:
5:
1469:
1467:
1459:
1458:
1453:
1448:
1438:
1437:
1434:
1433:
1418:
1403:
1388:
1379:
1370:
1364:
1351:
1344:
1335:
1332:
1331:
1330:
1321:
1311:
1299:
1293:
1276:
1262:
1249:
1240:, 1994, SIAM.
1232:
1229:
1227:
1226:
1192:
1171:
1152:
1128:
1101:(3): 388–414.
1083:
1068:
1047:
1037:, 1994, SIAM.
1019:
997:
974:
959:
937:
935:
932:
931:
930:
925:
919:
912:
905:
892:
889:
865:
862:
855:
854:
843:
838:
834:
831:
828:
825:
822:
819:
814:
810:
805:
801:
798:
794:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
759:
755:
752:
749:
746:
743:
740:
736:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
701:
697:
694:
691:
687:
680:
677:
671:
668:
665:
662:
659:
656:
651:
647:
628:
627:
615:
612:
609:
604:
599:
583:
582:
571:
567:
562:
558:
554:
549:
543:
538:
534:
531:
528:
525:
522:
519:
514:
509:
502:
498:
493:
489:
486:
482:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
447:
443:
440:
437:
434:
431:
428:
424:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
389:
385:
382:
379:
375:
368:
365:
359:
356:
353:
350:
347:
344:
341:
311:
310:
299:
295:
290:
286:
282:
277:
271:
263:
259:
254:
251:
247:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
210:
206:
202:
199:
196:
190:
183:
178:
175:
169:
166:
163:
160:
155:
151:
129:Main article:
126:
123:
58:linear systems
24:
14:
13:
10:
9:
6:
4:
3:
2:
1468:
1457:
1454:
1452:
1449:
1447:
1444:
1443:
1441:
1431:
1427:
1423:
1419:
1416:
1415:9781420034394
1412:
1409:. CRC Press.
1408:
1404:
1401:
1400:9781483137858
1397:
1393:
1389:
1385:
1380:
1376:
1371:
1367:
1365:0-471-30932-X
1361:
1357:
1352:
1349:
1345:
1342:
1338:
1337:
1333:
1328:
1325:
1322:
1319:
1315:
1312:
1309:
1308:
1303:
1300:
1296:
1290:
1286:
1282:
1277:
1273:
1269:
1265:
1263:0-89871-461-3
1259:
1255:
1250:
1247:
1246:0-89871-321-8
1243:
1239:
1235:
1234:
1230:
1223:
1222:0-89871-462-1
1219:
1215:
1211:
1210:
1206:
1203:
1196:
1193:
1189:
1188:
1183:
1178:
1176:
1172:
1167:
1163:
1159:
1155:
1153:0-471-90170-9
1149:
1145:
1141:
1135:
1133:
1129:
1124:
1120:
1116:
1112:
1108:
1104:
1100:
1096:
1095:
1087:
1084:
1079:
1075:
1071:
1069:0-471-09725-X
1065:
1061:
1057:
1051:
1048:
1044:
1043:0-89871-321-8
1040:
1036:
1032:
1026:
1024:
1020:
1016:
1013:
1008:
1006:
1004:
1002:
998:
994:
990:
985:
983:
981:
979:
975:
970:
966:
962:
960:0-89871-461-3
956:
952:
945:
943:
939:
933:
929:
926:
923:
920:
917:
913:
910:
909:Jacobi method
906:
903:
899:
895:
894:
890:
888:
886:
882:
878:
874:
872:
863:
861:
858:
841:
836:
829:
826:
823:
817:
812:
808:
803:
796:
792:
788:
785:
782:
776:
773:
767:
764:
761:
757:
753:
747:
744:
738:
734:
730:
727:
724:
718:
715:
709:
706:
703:
699:
695:
689:
685:
678:
675:
669:
663:
660:
657:
649:
645:
637:
636:
635:
633:
613:
610:
607:
602:
588:
587:
586:
569:
560:
556:
541:
536:
529:
526:
523:
517:
512:
500:
496:
491:
484:
480:
476:
473:
470:
464:
461:
455:
452:
449:
445:
441:
435:
432:
426:
422:
418:
415:
412:
406:
403:
397:
394:
391:
387:
383:
377:
373:
366:
363:
357:
351:
348:
345:
339:
332:
331:
330:
328:
324:
320:
316:
297:
288:
284:
269:
261:
257:
249:
245:
241:
235:
232:
226:
220:
217:
214:
208:
204:
200:
194:
188:
181:
176:
173:
164:
158:
153:
149:
138:
137:
136:
132:
124:
122:
120:
116:
112:
108:
104:
99:
97:
93:
89:
85:
80:
78:
74:
70:
66:
63:
59:
56:
51:
49:
45:
41:
37:
30:
19:
1421:
1406:
1391:
1383:
1374:
1355:
1347:
1340:
1326:
1317:
1305:
1284:
1253:
1237:
1200:
1195:
1185:
1165:
1143:
1098:
1092:
1086:
1059:
1050:
1034:
1014:
992:
950:
885:interpolated
880:
875:
867:
859:
856:
631:
629:
584:
326:
322:
318:
314:
312:
134:
100:
81:
52:
46:for solving
39:
33:
1302:Yousef Saad
1182:Yousef Saad
119:approximate
113:methods in
1440:Categories
1231:References
1140:Minoux, M.
111:relaxation
86:, such as
804:−
793:−
777:φ
758:−
748:φ
719:φ
690:φ
650:∗
646:φ
608:φ
598:∇
518:φ
508:∇
492:−
481:−
465:φ
446:−
436:φ
407:φ
378:φ
340:φ
236:φ
221:φ
215:−
205:−
195:φ
159:φ
103:smoothing
1205:Archived
1142:(1986).
891:See also
117:, which
1272:1744713
1162:0868279
1123:0594854
1115:3689446
1078:0720547
969:1744713
1428:
1413:
1398:
1362:
1291:
1270:
1260:
1244:
1220:
1160:
1150:
1121:
1113:
1076:
1066:
1041:
967:
957:
55:sparse
1316:2002
1111:JSTOR
991:2002
934:Notes
1426:ISBN
1411:ISBN
1396:ISBN
1360:ISBN
1289:ISBN
1258:ISBN
1242:ISBN
1218:ISBN
1148:ISBN
1064:ISBN
1039:ISBN
955:ISBN
914:The
907:The
42:are
1103:doi
67:of
34:In
1442::
1304:,
1283:.
1268:MR
1266:.
1216:,
1184:,
1174:^
1158:MR
1156:.
1131:^
1119:MR
1117:.
1109:.
1097:.
1074:MR
1072:.
1033:,
1022:^
1000:^
977:^
965:MR
963:.
941:^
325:,
317:,
38:,
1432:.
1417:.
1402:.
1368:.
1297:.
1274:.
1248:.
1224:.
1125:.
1105::
1099:5
1080:.
1045:.
971:.
904:.
881:h
842:,
837:)
833:)
830:y
827:,
824:x
821:(
818:f
813:2
809:h
800:)
797:h
789:y
786:,
783:x
780:(
774:+
771:)
768:y
765:,
762:h
754:x
751:(
745:+
742:)
739:h
735:+
731:y
728:,
725:x
722:(
716:+
713:)
710:y
707:,
704:h
700:+
696:x
693:(
686:(
679:4
676:1
670:=
667:)
664:y
661:,
658:x
655:(
632:h
614:f
611:=
603:2
570:.
566:)
561:4
557:h
553:(
548:O
542:+
537:)
533:)
530:y
527:,
524:x
521:(
513:2
501:2
497:h
488:)
485:h
477:y
474:,
471:x
468:(
462:+
459:)
456:y
453:,
450:h
442:x
439:(
433:+
430:)
427:h
423:+
419:y
416:,
413:x
410:(
404:+
401:)
398:y
395:,
392:h
388:+
384:x
381:(
374:(
367:4
364:1
358:=
355:)
352:y
349:,
346:x
343:(
327:y
323:x
319:y
315:x
298:.
294:)
289:2
285:h
281:(
276:O
270:+
262:2
258:h
253:)
250:h
246:+
242:x
239:(
233:+
230:)
227:x
224:(
218:2
212:)
209:h
201:x
198:(
189:=
182:2
177:x
174:d
168:)
165:x
162:(
154:2
150:d
31:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.