1641:
928:
791:
1636:{\displaystyle {\begin{aligned}&\mathbf {x} _{0}:={\text{Some initial guess}}\\&\mathbf {r} _{0}:=\mathbf {M} ^{-1}(\mathbf {b} -\mathbf {Ax} _{0})\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&{\text{Iterate, with }}k{\text{ starting at }}0:\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {M} ^{-1}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {M} ^{-1}\mathbf {Ap} _{k}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad \mathbf {Ap} _{k+1}:=\mathbf {A} \mathbf {r} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\\&\qquad k:=k+1\\\end{aligned}}}
137:
786:{\displaystyle {\begin{aligned}&\mathbf {x} _{0}:={\text{Some initial guess}}\\&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&{\text{Iterate, with }}k{\text{ starting at }}0:\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {Ar} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad \mathbf {Ap} _{k+1}:=\mathbf {Ar} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\\&\qquad k:=k+1\end{aligned}}}
75:
933:
142:
1679:
909:
823:
129:
850:
922:
By making a few substitutions and variable changes, a preconditioned conjugate residual method may be derived in the same way as done for the conjugate gradient method:
877:
1702:
1681:
must be symmetric positive definite. Note that the residual vector here is different from the residual vector without preconditioning.
1718:
914:
Note: the above algorithm can be transformed so to make only one symmetric matrix-vector multiplication in each iteration.
45:
25:
825:
has been deemed converged. The only difference between this and the conjugate gradient method is the calculation of
96:
33:
29:
1652:
882:
799:
105:
828:
855:
1698:
85:
1647:
21:
1712:
1690:
99:. It involves more numerical operations and requires more storage.
95:
The conjugate residual method differs from the closely related
39:
This method is used to solve linear equations of the form
36:, with similar construction and convergence properties.
102:
Given an (arbitrary) initial estimate of the solution
1655:
931:
885:
858:
831:
802:
140:
108:
70:{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }
48:
1673:
1635:
903:
871:
844:
817:
785:
123:
69:
879:(plus the optional incremental calculation of
8:
1695:Iterative methods for sparse linear systems
1662:
1657:
1654:
1602:
1594:
1587:
1568:
1563:
1557:
1542:
1534:
1521:
1516:
1509:
1490:
1485:
1469:
1464:
1448:
1443:
1437:
1430:
1429:
1424:
1419:
1404:
1399:
1393:
1386:
1385:
1374:
1369:
1365:
1356:
1340:
1332:
1322:
1317:
1310:
1297:
1292:
1276:
1271:
1258:
1253:
1246:
1233:
1228:
1212:
1207:
1191:
1183:
1173:
1168:
1160:
1159:
1149:
1141:
1129:
1124:
1118:
1111:
1110:
1105:
1100:
1096:
1087:
1066:
1058:
1047:
1042:
1032:
1027:
1012:
1004:
995:
983:
978:
968:
963:
952:
943:
938:
932:
930:
895:
887:
884:
863:
857:
836:
830:
809:
804:
801:
752:
744:
737:
718:
710:
694:
686:
673:
668:
661:
642:
637:
621:
616:
600:
592:
584:
583:
578:
573:
558:
550:
542:
541:
530:
525:
521:
512:
496:
488:
481:
468:
463:
447:
442:
429:
424:
417:
404:
399:
383:
378:
362:
354:
346:
345:
335:
327:
315:
307:
299:
298:
293:
288:
284:
275:
254:
246:
235:
230:
220:
215:
203:
195:
186:
177:
172:
161:
152:
147:
141:
139:
115:
110:
107:
62:
54:
49:
47:
32:very similar to the much more popular
7:
1431:
1387:
1161:
1112:
796:the iteration may be stopped once
585:
543:
347:
300:
14:
1674:{\displaystyle \mathbf {M} ^{-1}}
904:{\displaystyle \mathbf {Ap} _{k}}
1658:
1598:
1595:
1564:
1558:
1538:
1535:
1517:
1486:
1465:
1444:
1438:
1420:
1400:
1394:
1370:
1336:
1333:
1318:
1293:
1272:
1254:
1229:
1208:
1187:
1184:
1169:
1145:
1142:
1125:
1119:
1101:
1043:
1028:
1008:
1005:
996:
979:
964:
939:
891:
888:
818:{\displaystyle \mathbf {x} _{k}}
805:
748:
745:
714:
711:
690:
687:
669:
638:
617:
596:
593:
574:
554:
551:
526:
492:
489:
464:
443:
425:
400:
379:
358:
355:
331:
328:
311:
308:
289:
231:
216:
199:
196:
187:
173:
148:
131:, the method is outlined below:
124:{\displaystyle \mathbf {x} _{0}}
111:
63:
55:
50:
1613:
1532:
1462:
1351:
1269:
1205:
1082:
763:
684:
614:
507:
440:
376:
270:
1156:
1137:
1018:
992:
342:
323:
1:
1697:(2nd ed.), page 194, SIAM.
845:{\displaystyle \alpha _{k}}
26:systems of linear equations
1735:
872:{\displaystyle \beta _{k}}
97:conjugate gradient method
34:conjugate gradient method
18:conjugate residual method
1719:Numerical linear algebra
1068: starting at
256: starting at
1675:
1637:
905:
873:
846:
819:
787:
125:
71:
30:Krylov subspace method
1676:
1638:
906:
874:
847:
820:
788:
126:
84:is an invertible and
72:
1653:
929:
883:
856:
829:
800:
138:
106:
46:
1436:
1392:
1117:
1060:Iterate, with
590:
548:
305:
248:Iterate, with
1671:
1633:
1631:
1418:
1368:
1099:
954:Some initial guess
901:
869:
842:
815:
783:
781:
572:
524:
287:
163:Some initial guess
121:
67:
1703:978-0-89871-534-7
1455:
1198:
1069:
1061:
955:
607:
369:
257:
249:
164:
24:used for solving
1726:
1680:
1678:
1677:
1672:
1670:
1669:
1661:
1642:
1640:
1639:
1634:
1632:
1611:
1607:
1606:
1601:
1592:
1591:
1579:
1578:
1567:
1561:
1553:
1552:
1541:
1530:
1526:
1525:
1520:
1514:
1513:
1501:
1500:
1489:
1480:
1479:
1468:
1460:
1456:
1454:
1453:
1452:
1447:
1441:
1435:
1434:
1428:
1423:
1416:
1415:
1414:
1403:
1397:
1391:
1390:
1384:
1373:
1366:
1361:
1360:
1349:
1345:
1344:
1339:
1330:
1329:
1321:
1315:
1314:
1302:
1301:
1296:
1287:
1286:
1275:
1267:
1263:
1262:
1257:
1251:
1250:
1238:
1237:
1232:
1223:
1222:
1211:
1203:
1199:
1197:
1196:
1195:
1190:
1181:
1180:
1172:
1166:
1165:
1164:
1154:
1153:
1148:
1135:
1134:
1133:
1128:
1122:
1116:
1115:
1109:
1104:
1097:
1092:
1091:
1080:
1070:
1067:
1062:
1059:
1056:
1052:
1051:
1046:
1037:
1036:
1031:
1024:
1017:
1016:
1011:
999:
991:
990:
982:
973:
972:
967:
960:
956:
953:
948:
947:
942:
935:
910:
908:
907:
902:
900:
899:
894:
878:
876:
875:
870:
868:
867:
851:
849:
848:
843:
841:
840:
824:
822:
821:
816:
814:
813:
808:
792:
790:
789:
784:
782:
761:
757:
756:
751:
742:
741:
729:
728:
717:
705:
704:
693:
682:
678:
677:
672:
666:
665:
653:
652:
641:
632:
631:
620:
612:
608:
606:
605:
604:
599:
589:
588:
582:
577:
570:
569:
568:
557:
547:
546:
540:
529:
522:
517:
516:
505:
501:
500:
495:
486:
485:
473:
472:
467:
458:
457:
446:
438:
434:
433:
428:
422:
421:
409:
408:
403:
394:
393:
382:
374:
370:
368:
367:
366:
361:
352:
351:
350:
340:
339:
334:
321:
320:
319:
314:
304:
303:
297:
292:
285:
280:
279:
268:
258:
255:
250:
247:
244:
240:
239:
234:
225:
224:
219:
212:
208:
207:
202:
190:
182:
181:
176:
169:
165:
162:
157:
156:
151:
144:
130:
128:
127:
122:
120:
119:
114:
86:Hermitian matrix
76:
74:
73:
68:
66:
58:
53:
20:is an iterative
1734:
1733:
1729:
1728:
1727:
1725:
1724:
1723:
1709:
1708:
1687:
1656:
1651:
1650:
1630:
1629:
1609:
1608:
1593:
1583:
1562:
1533:
1528:
1527:
1515:
1505:
1484:
1463:
1458:
1457:
1442:
1417:
1398:
1367:
1352:
1347:
1346:
1331:
1316:
1306:
1291:
1270:
1265:
1264:
1252:
1242:
1227:
1206:
1201:
1200:
1182:
1167:
1155:
1140:
1136:
1123:
1098:
1083:
1078:
1077:
1054:
1053:
1041:
1026:
1022:
1021:
1003:
977:
962:
958:
957:
937:
927:
926:
920:
918:Preconditioning
886:
881:
880:
859:
854:
853:
832:
827:
826:
803:
798:
797:
780:
779:
759:
758:
743:
733:
709:
685:
680:
679:
667:
657:
636:
615:
610:
609:
591:
571:
549:
523:
508:
503:
502:
487:
477:
462:
441:
436:
435:
423:
413:
398:
377:
372:
371:
353:
341:
326:
322:
306:
286:
271:
266:
265:
242:
241:
229:
214:
210:
209:
194:
171:
167:
166:
146:
136:
135:
109:
104:
103:
44:
43:
12:
11:
5:
1732:
1730:
1722:
1721:
1711:
1710:
1707:
1706:
1686:
1683:
1668:
1665:
1660:
1648:preconditioner
1644:
1643:
1628:
1625:
1622:
1619:
1616:
1612:
1610:
1605:
1600:
1597:
1590:
1586:
1582:
1577:
1574:
1571:
1566:
1560:
1556:
1551:
1548:
1545:
1540:
1537:
1531:
1529:
1524:
1519:
1512:
1508:
1504:
1499:
1496:
1493:
1488:
1483:
1478:
1475:
1472:
1467:
1461:
1459:
1451:
1446:
1440:
1433:
1427:
1422:
1413:
1410:
1407:
1402:
1396:
1389:
1383:
1380:
1377:
1372:
1364:
1359:
1355:
1350:
1348:
1343:
1338:
1335:
1328:
1325:
1320:
1313:
1309:
1305:
1300:
1295:
1290:
1285:
1282:
1279:
1274:
1268:
1266:
1261:
1256:
1249:
1245:
1241:
1236:
1231:
1226:
1221:
1218:
1215:
1210:
1204:
1202:
1194:
1189:
1186:
1179:
1176:
1171:
1163:
1158:
1152:
1147:
1144:
1139:
1132:
1127:
1121:
1114:
1108:
1103:
1095:
1090:
1086:
1081:
1079:
1076:
1073:
1065:
1057:
1055:
1050:
1045:
1040:
1035:
1030:
1025:
1023:
1020:
1015:
1010:
1007:
1002:
998:
994:
989:
986:
981:
976:
971:
966:
961:
959:
951:
946:
941:
936:
934:
919:
916:
898:
893:
890:
866:
862:
839:
835:
812:
807:
794:
793:
778:
775:
772:
769:
766:
762:
760:
755:
750:
747:
740:
736:
732:
727:
724:
721:
716:
713:
708:
703:
700:
697:
692:
689:
683:
681:
676:
671:
664:
660:
656:
651:
648:
645:
640:
635:
630:
627:
624:
619:
613:
611:
603:
598:
595:
587:
581:
576:
567:
564:
561:
556:
553:
545:
539:
536:
533:
528:
520:
515:
511:
506:
504:
499:
494:
491:
484:
480:
476:
471:
466:
461:
456:
453:
450:
445:
439:
437:
432:
427:
420:
416:
412:
407:
402:
397:
392:
389:
386:
381:
375:
373:
365:
360:
357:
349:
344:
338:
333:
330:
325:
318:
313:
310:
302:
296:
291:
283:
278:
274:
269:
267:
264:
261:
253:
245:
243:
238:
233:
228:
223:
218:
213:
211:
206:
201:
198:
193:
189:
185:
180:
175:
170:
168:
160:
155:
150:
145:
143:
118:
113:
78:
77:
65:
61:
57:
52:
22:numeric method
13:
10:
9:
6:
4:
3:
2:
1731:
1720:
1717:
1716:
1714:
1704:
1700:
1696:
1692:
1689:
1688:
1684:
1682:
1666:
1663:
1649:
1626:
1623:
1620:
1617:
1614:
1603:
1588:
1584:
1580:
1575:
1572:
1569:
1554:
1549:
1546:
1543:
1522:
1510:
1506:
1502:
1497:
1494:
1491:
1481:
1476:
1473:
1470:
1449:
1425:
1411:
1408:
1405:
1381:
1378:
1375:
1362:
1357:
1353:
1341:
1326:
1323:
1311:
1307:
1303:
1298:
1288:
1283:
1280:
1277:
1259:
1247:
1243:
1239:
1234:
1224:
1219:
1216:
1213:
1192:
1177:
1174:
1150:
1130:
1106:
1093:
1088:
1084:
1074:
1071:
1063:
1048:
1038:
1033:
1013:
1000:
987:
984:
974:
969:
949:
944:
925:
924:
923:
917:
915:
912:
911:at the end).
896:
864:
860:
837:
833:
810:
776:
773:
770:
767:
764:
753:
738:
734:
730:
725:
722:
719:
706:
701:
698:
695:
674:
662:
658:
654:
649:
646:
643:
633:
628:
625:
622:
601:
579:
565:
562:
559:
537:
534:
531:
518:
513:
509:
497:
482:
478:
474:
469:
459:
454:
451:
448:
430:
418:
414:
410:
405:
395:
390:
387:
384:
363:
336:
316:
294:
281:
276:
272:
262:
259:
251:
236:
226:
221:
204:
191:
183:
178:
158:
153:
134:
133:
132:
116:
100:
98:
93:
91:
87:
83:
59:
42:
41:
40:
37:
35:
31:
27:
23:
19:
1694:
1645:
921:
913:
795:
101:
94:
92:is nonzero.
89:
81:
79:
38:
17:
15:
1691:Yousef Saad
1685:References
1664:−
1585:β
1507:β
1354:β
1324:−
1308:α
1304:−
1244:α
1175:−
1085:α
1001:−
985:−
861:β
834:α
735:β
659:β
510:β
479:α
475:−
415:α
273:α
192:−
28:. It's a
1713:Category
1701:
88:, and
80:where
1699:ISBN
1646:The
852:and
16:The
1715::
1693:,
1618::=
1555::=
1482::=
1363::=
1289::=
1225::=
1094::=
1039::=
975::=
950::=
768::=
707::=
634::=
519::=
460::=
396::=
282::=
227::=
184::=
159::=
1705:.
1667:1
1659:M
1627:1
1624:+
1621:k
1615:k
1604:k
1599:p
1596:A
1589:k
1581:+
1576:1
1573:+
1570:k
1565:r
1559:A
1550:1
1547:+
1544:k
1539:p
1536:A
1523:k
1518:p
1511:k
1503:+
1498:1
1495:+
1492:k
1487:r
1477:1
1474:+
1471:k
1466:p
1450:k
1445:r
1439:A
1432:T
1426:k
1421:r
1412:1
1409:+
1406:k
1401:r
1395:A
1388:T
1382:1
1379:+
1376:k
1371:r
1358:k
1342:k
1337:p
1334:A
1327:1
1319:M
1312:k
1299:k
1294:r
1284:1
1281:+
1278:k
1273:r
1260:k
1255:p
1248:k
1240:+
1235:k
1230:x
1220:1
1217:+
1214:k
1209:x
1193:k
1188:p
1185:A
1178:1
1170:M
1162:T
1157:)
1151:k
1146:p
1143:A
1138:(
1131:k
1126:r
1120:A
1113:T
1107:k
1102:r
1089:k
1075::
1072:0
1064:k
1049:0
1044:r
1034:0
1029:p
1019:)
1014:0
1009:x
1006:A
997:b
993:(
988:1
980:M
970:0
965:r
945:0
940:x
897:k
892:p
889:A
865:k
838:k
811:k
806:x
777:1
774:+
771:k
765:k
754:k
749:p
746:A
739:k
731:+
726:1
723:+
720:k
715:r
712:A
702:1
699:+
696:k
691:p
688:A
675:k
670:p
663:k
655:+
650:1
647:+
644:k
639:r
629:1
626:+
623:k
618:p
602:k
597:r
594:A
586:T
580:k
575:r
566:1
563:+
560:k
555:r
552:A
544:T
538:1
535:+
532:k
527:r
514:k
498:k
493:p
490:A
483:k
470:k
465:r
455:1
452:+
449:k
444:r
431:k
426:p
419:k
411:+
406:k
401:x
391:1
388:+
385:k
380:x
364:k
359:p
356:A
348:T
343:)
337:k
332:p
329:A
324:(
317:k
312:r
309:A
301:T
295:k
290:r
277:k
263::
260:0
252:k
237:0
232:r
222:0
217:p
205:0
200:x
197:A
188:b
179:0
174:r
154:0
149:x
117:0
112:x
90:b
82:A
64:b
60:=
56:x
51:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.