import numpy as np ### Testdaten ################################################################## A1 = np.array([[2.0, 1.0, 7.0], [8.0, 8.0, 33.0], [-4.0, 10.0, 4.0]]) b1 = np.array([ 15.0, 73.0, 12.0 ]) A2 = np.array([ [ 2., 1., 1., 0. ], [ 4., 3., 3., 1. ], [ 8., 7., 9., 5. ], [ 6., 7., 9., 8. ]]) b2 = np.array([ 13., 32., 76., 71. ]) A3 = np.array([ [ 5.0, 2.0, 5.0, 1.0, 3.0, 6.0, 6.0, 1.0, 8.0, 1.0 ], [ 45.0, 21.0, 48.0, 11.0, 30.0, 63.0, 62.0, 11.0, 81.0, 11.0 ], [ 20.0, 35.0, 49.0, 22.0, 46.0, 112.0, 101.0, 31.0, 114.0, 31.0 ], [ 0.0, 12.0, 20.0, 17.0, 40.0, 68.0, 59.0, 51.0, 44.0, 50.0 ], [ 30.0, 27.0, 49.0, 52.0, 56.0, 119.0, 116.0, 62.0, 117.0, 66.0 ], [ 10.0, 22.0, 46.0, 59.0, 168.0, 230.0, 161.0, 132.0, 159.0, 203.0 ], [ 15.0, 9.0, 30.0, 5.0, 117.0, 170.0, 94.0, 69.0, 120.0, 152.0 ], [ 25.0, 10.0, 43.0, 32.0, 132.0, 171.0, 195.0, 112.0, 192.0, 231.0 ], [ 40.0, 28.0, 70.0, 25.0, 126.0, 220.0, 225.0, 116.0, 246.0, 228.0 ], [ 20.0, 23.0, 43.0, 86.0, 100.0, 223.0, 231.0, 125.0, 328.0, 308.0 ]]) b3 = np.array([ 195.0, 1953.0, 2698.0, 1533.0, 3350.0, 5075.0, 3271.0, 5388.0, 6297.0, 7494.0 ]) A4 = np.array( [[3.0, 6.0, -7.0, 1.0, -9.0, -6.0, -5.0, -3.0, 1.0, 10.0, 3.0, 6.0, -7.0, 1.0, -5.0, 5.0, 1.0, 7.0, 9.0, -5.0, 1.0, 2.0, -9.0, 0.0, -5.0, -2.0, -8.0, -3.0, -5.0, 8.0, -1.0, -3.0, 3.0, 3.0, 0.0, -10.0, -6.0, -3.0, 9.0, 10.0, -7.0, 0.0, -6.0, -4.0, -1.0, -9.0, -2.0, -4.0, 4.0, -3.0], [-3.0, -6.0, 7.0, 9.0, 1.0, -1.0, 6.0, -9.0, 5.0, 2.0, 1.0, 3.0, -7.0, 5.0, 7.0, -8.0, 2.0, 4.0, -10.0, 5.0, 2.0, 8.0, 7.0, 6.0, 0.0, -8.0, -7.0, -4.0, -5.0, 10.0, 8.0, -1.0, 4.0, 7.0, -2.0, 7.0, 10.0, -10.0, 6.0, 9.0, -6.0, -8.0, 10.0, 3.0, 9.0, -8.0, 5.0, 5.0, 1.0, -6.0], [-3.0, 0.0, 1.0, -9.0, -9.0, 0.0, 5.0, -10.0, 1.0, 1.0, 1.0, -10.0, 6.0, 8.0, -6.0, -8.0, 3.0, 10.0, -2.0, 7.0, 0.0, -9.0, -9.0, -1.0, -9.0, 10.0, -4.0, 7.0, 6.0, -6.0, 8.0, 7.0, -1.0, 0.0, -1.0, -6.0, 1.0, -1.0, 5.0, 1.0, -9.0, 3.0, 0.0, -1.0, -10.0, -10.0, 5.0, -1.0, 9.0, 8.0], [-10.0, -3.0, 10.0, 10.0, 6.0, 3.0, 3.0, -2.0, -1.0, 4.0, 5.0, 0.0, -3.0, 0.0, 1.0, -10.0, -10.0, 0.0, 6.0, 2.0, 0.0, -3.0, 5.0, -1.0, 10.0, 8.0, -6.0, 8.0, -1.0, 10.0, -8.0, 1.0, 4.0, 10.0, -8.0, -8.0, -1.0, -1.0, -3.0, 5.0, -5.0, -8.0, -4.0, -6.0, 0.0, 0.0, -5.0, 3.0, 8.0, -3.0], [1.0, -4.0, -9.0, 8.0, -1.0, 0.0, 4.0, 6.0, 3.0, -1.0, 1.0, 8.0, -9.0, -5.0, 1.0, -5.0, -8.0, -5.0, -8.0, -8.0, 5.0, -8.0, -9.0, 0.0, -5.0, -3.0, -9.0, 7.0, 4.0, 9.0, 10.0, 2.0, -4.0, -8.0, -8.0, 8.0, -8.0, -2.0, -9.0, 8.0, 5.0, -2.0, -2.0, -5.0, -3.0, 4.0, -6.0, -2.0, -5.0, -10.0], [4.0, 7.0, 7.0, 4.0, 1.0, 9.0, 6.0, 0.0, -2.0, -4.0, 4.0, -5.0, 8.0, -9.0, -9.0, 1.0, 6.0, -5.0, 10.0, -3.0, 0.0, -4.0, 5.0, 6.0, -7.0, -7.0, 0.0, 10.0, 0.0, -4.0, -7.0, -10.0, 2.0, -8.0, 5.0, -10.0, 6.0, 2.0, 4.0, 9.0, -9.0, -3.0, 2.0, -5.0, -3.0, 9.0, 10.0, 0.0, 6.0, 1.0], [-5.0, -6.0, 7.0, 1.0, -4.0, 0.0, -4.0, 1.0, 4.0, 8.0, 5.0, -4.0, 9.0, 3.0, -9.0, 4.0, -5.0, -6.0, 3.0, 0.0, 7.0, -6.0, -3.0, -8.0, 3.0, -7.0, 1.0, 4.0, -9.0, -3.0, 3.0, 4.0, -3.0, 0.0, 2.0, 6.0, 0.0, -2.0, -5.0, 6.0, -7.0, 3.0, 9.0, -5.0, 6.0, -2.0, 1.0, -4.0, -7.0, -1.0], [4.0, 2.0, 2.0, 8.0, 9.0, -7.0, 3.0, 6.0, 10.0, 0.0, 10.0, -4.0, 7.0, 3.0, 7.0, -4.0, 9.0, 3.0, -9.0, 6.0, 9.0, -10.0, -4.0, 9.0, -5.0, 10.0, -7.0, -5.0, 3.0, 5.0, -8.0, -10.0, 8.0, -5.0, -5.0, 0.0, -10.0, -6.0, 6.0, -10.0, 5.0, 1.0, -5.0, 3.0, -7.0, 8.0, 1.0, 0.0, -2.0, -7.0], [-1.0, 1.0, -4.0, 7.0, 0.0, 4.0, 2.0, -8.0, -3.0, -6.0, -5.0, -7.0, -8.0, -3.0, 1.0, 4.0, 5.0, 10.0, 3.0, -6.0, -8.0, 1.0, 6.0, -2.0, -9.0, 0.0, -9.0, -10.0, 2.0, 9.0, 6.0, -1.0, -9.0, -1.0, -1.0, 3.0, -4.0, 10.0, -10.0, 7.0, -10.0, -7.0, -4.0, -5.0, 2.0, 8.0, 10.0, -9.0, 8.0, -10.0], [-2.0, 4.0, 1.0, 9.0, -4.0, 2.0, 5.0, 9.0, 0.0, 3.0, 5.0, -1.0, -7.0, 2.0, 6.0, -9.0, 2.0, 10.0, -6.0, -4.0, 6.0, -4.0, 1.0, -5.0, -3.0, 6.0, -4.0, -5.0, 2.0, -6.0, -7.0, 5.0, -1.0, 1.0, 5.0, -1.0, 8.0, 8.0, -7.0, -5.0, 10.0, -1.0, -7.0, 8.0, 9.0, -8.0, 1.0, 1.0, -1.0, 0.0], [-4.0, -6.0, -5.0, -2.0, 3.0, -1.0, 6.0, 1.0, 8.0, -5.0, 8.0, 0.0, 4.0, 5.0, -4.0, 1.0, -4.0, 6.0, 8.0, 10.0, 1.0, 5.0, -10.0, 4.0, -9.0, 8.0, 7.0, 2.0, 1.0, 0.0, 10.0, -1.0, 3.0, 3.0, 3.0, 7.0, 10.0, -6.0, 0.0, 3.0, 0.0, -4.0, 2.0, -4.0, -10.0, -2.0, -4.0, 2.0, 1.0, -1.0], [8.0, 9.0, -2.0, -6.0, 4.0, 2.0, -1.0, 3.0, 4.0, 5.0, -5.0, -4.0, -9.0, 2.0, -9.0, 4.0, 5.0, 1.0, -4.0, -6.0, -7.0, -9.0, 9.0, -2.0, -6.0, 5.0, 2.0, -1.0, 1.0, 4.0, 10.0, 0.0, 2.0, 10.0, 10.0, -4.0, -6.0, 6.0, -8.0, 4.0, 8.0, 7.0, 7.0, -1.0, -2.0, -2.0, 5.0, 3.0, 0.0, -1.0], [-8.0, 0.0, -7.0, -6.0, -7.0, -8.0, 2.0, -4.0, 7.0, -4.0, 8.0, -4.0, -8.0, 7.0, 10.0, 4.0, 2.0, -10.0, -9.0, 2.0, 6.0, 6.0, 6.0, -5.0, 4.0, -10.0, 2.0, -2.0, 8.0, 7.0, -3.0, 4.0, 1.0, 2.0, -8.0, -1.0, -9.0, 4.0, -1.0, -1.0, 4.0, 2.0, -6.0, -9.0, -8.0, -5.0, 0.0, -8.0, 7.0, 6.0], [5.0, 5.0, 5.0, -9.0, -1.0, -1.0, -8.0, 0.0, 3.0, 4.0, -4.0, -5.0, 6.0, 9.0, -8.0, -10.0, -3.0, 4.0, 4.0, 4.0, -4.0, -6.0, 1.0, 5.0, 7.0, -3.0, 0.0, -2.0, 10.0, 3.0, -3.0, -1.0, 1.0, 0.0, 8.0, 10.0, -3.0, 2.0, 6.0, -8.0, 3.0, 6.0, -10.0, -1.0, 8.0, -7.0, -10.0, 4.0, -1.0, -6.0], [1.0, 4.0, -4.0, -7.0, 7.0, 3.0, -2.0, 10.0, -4.0, -9.0, 6.0, 0.0, 3.0, -8.0, -3.0, -5.0, -7.0, 8.0, 10.0, -4.0, 10.0, 3.0, 0.0, 0.0, -2.0, 4.0, 3.0, 8.0, -1.0, -9.0, -8.0, 3.0, -3.0, 2.0, -6.0, 8.0, -10.0, 0.0, 0.0, -8.0, -9.0, -5.0, 6.0, -2.0, 9.0, -4.0, -7.0, -7.0, 10.0, 5.0], [-1.0, 7.0, 10.0, -7.0, -9.0, -3.0, -4.0, -5.0, 5.0, -2.0, -6.0, 3.0, -7.0, -9.0, 0.0, -5.0, 7.0, 5.0, -7.0, 0.0, -3.0, -5.0, 8.0, 3.0, -6.0, 4.0, 10.0, 10.0, -4.0, 10.0, 1.0, -4.0, 9.0, 7.0, -5.0, 0.0, -10.0, 7.0, -2.0, -10.0, -9.0, -6.0, 1.0, -1.0, -8.0, -7.0, 5.0, 3.0, -6.0, -7.0], [-6.0, 1.0, -9.0, 0.0, -10.0, -8.0, -10.0, -2.0, 8.0, 7.0, 5.0, 9.0, 8.0, -7.0, 2.0, -3.0, 7.0, 10.0, -5.0, 10.0, -4.0, 7.0, 10.0, -6.0, 6.0, -3.0, 5.0, 5.0, -4.0, -1.0, 9.0, 6.0, 0.0, 9.0, 8.0, 8.0, 3.0, -2.0, -10.0, -9.0, 2.0, 0.0, -6.0, -7.0, 6.0, 7.0, 8.0, -8.0, -7.0, -7.0], [8.0, 4.0, -7.0, 1.0, 6.0, -9.0, -6.0, 1.0, 5.0, 9.0, 2.0, -5.0, -3.0, -2.0, 1.0, -9.0, -4.0, 5.0, 3.0, -8.0, -6.0, -9.0, 1.0, -7.0, 10.0, 1.0, 10.0, 10.0, 9.0, -10.0, 7.0, 0.0, 8.0, -9.0, -5.0, -3.0, -7.0, 7.0, 9.0, 0.0, 2.0, 9.0, -3.0, 5.0, 8.0, -6.0, 1.0, -1.0, 7.0, -4.0], [10.0, 10.0, 9.0, -4.0, 5.0, 5.0, 8.0, 8.0, 4.0, -1.0, 6.0, 9.0, -6.0, 0.0, 7.0, -6.0, 1.0, 8.0, 9.0, 6.0, 7.0, 7.0, 4.0, -7.0, 2.0, -6.0, -2.0, 3.0, 3.0, 4.0, 1.0, -6.0, -3.0, -1.0, -2.0, 9.0, 3.0, -1.0, 9.0, 0.0, 7.0, -6.0, -9.0, -4.0, -1.0, -1.0, 5.0, -1.0, -9.0, -2.0], [-2.0, 5.0, -2.0, 0.0, -8.0, 10.0, 4.0, 2.0, 10.0, -7.0, 4.0, -4.0, -8.0, -6.0, 8.0, 5.0, 3.0, -4.0, -1.0, -9.0, 0.0, -2.0, -2.0, -9.0, -10.0, 9.0, 7.0, -1.0, -1.0, 4.0, 10.0, -1.0, -3.0, 10.0, 1.0, -8.0, -5.0, -7.0, 7.0, -9.0, 2.0, 1.0, -2.0, -3.0, 1.0, -8.0, 10.0, 7.0, -4.0, 3.0], [0.0, -9.0, -2.0, 0.0, 8.0, -5.0, -4.0, 5.0, 10.0, -6.0, -4.0, -6.0, 8.0, 7.0, 10.0, -10.0, 9.0, 0.0, -6.0, -6.0, 4.0, -4.0, 9.0, 8.0, -6.0, -8.0, -5.0, 6.0, -7.0, -9.0, -8.0, -10.0, 5.0, 10.0, -8.0, 9.0, -4.0, -3.0, -6.0, -6.0, 4.0, -10.0, -1.0, -2.0, -10.0, 10.0, 10.0, 0.0, 1.0, -8.0], [9.0, -3.0, 6.0, -4.0, 6.0, 10.0, 4.0, 3.0, 4.0, -1.0, 5.0, 2.0, 10.0, 0.0, 6.0, -10.0, -6.0, -7.0, 8.0, 6.0, 3.0, 3.0, -8.0, 5.0, -6.0, 6.0, -2.0, -7.0, 3.0, 10.0, -4.0, -4.0, -6.0, 3.0, 3.0, 8.0, -7.0, 3.0, -3.0, 7.0, -4.0, -4.0, -10.0, 3.0, -2.0, -4.0, 6.0, 7.0, -10.0, 6.0], [6.0, 8.0, -6.0, 10.0, 5.0, -5.0, 5.0, 0.0, 3.0, 1.0, -7.0, 9.0, 4.0, 2.0, 4.0, -5.0, 5.0, 3.0, -8.0, 2.0, 7.0, 4.0, -4.0, 4.0, 3.0, 0.0, 4.0, -5.0, -2.0, -3.0, 6.0, -6.0, 3.0, -2.0, -2.0, 6.0, -9.0, -2.0, -3.0, 4.0, -3.0, -2.0, 9.0, 1.0, 2.0, 2.0, 4.0, -9.0, -8.0, -7.0], [-2.0, -9.0, -3.0, -9.0, -7.0, -5.0, -5.0, -4.0, -4.0, 7.0, 1.0, -4.0, -7.0, 7.0, -1.0, 5.0, -8.0, 4.0, -3.0, 10.0, -6.0, -9.0, -7.0, 0.0, 0.0, 9.0, -3.0, 4.0, -4.0, 7.0, -9.0, 7.0, -5.0, -9.0, -2.0, -3.0, 6.0, -4.0, 0.0, 5.0, -5.0, -5.0, 5.0, 7.0, -4.0, -10.0, -3.0, -6.0, -4.0, 7.0], [-4.0, 4.0, -1.0, 8.0, 3.0, 10.0, -6.0, 9.0, -3.0, -6.0, -8.0, 7.0, 0.0, 5.0, 3.0, 0.0, -8.0, 4.0, 3.0, 6.0, 9.0, 9.0, 8.0, 10.0, 2.0, 7.0, 9.0, -8.0, -8.0, -4.0, 5.0, -5.0, -5.0, -5.0, 8.0, -3.0, -10.0, 2.0, 0.0, -7.0, -7.0, -8.0, 3.0, -10.0, 2.0, -10.0, 6.0, -8.0, 7.0, -10.0], [1.0, -1.0, 5.0, -8.0, 1.0, -2.0, 9.0, 10.0, 8.0, 5.0, 3.0, -4.0, 8.0, 7.0, 4.0, -6.0, -3.0, -1.0, -1.0, -6.0, 3.0, -3.0, -2.0, 8.0, -7.0, 0.0, 10.0, 3.0, 6.0, -2.0, -10.0, 0.0, 5.0, 0.0, -9.0, 5.0, -8.0, -1.0, 2.0, -3.0, -10.0, 3.0, -6.0, 10.0, -3.0, 9.0, -5.0, -1.0, 7.0, 10.0], [-9.0, -6.0, -1.0, -4.0, -10.0, 4.0, -5.0, 3.0, -5.0, 4.0, -7.0, -2.0, 4.0, -5.0, -9.0, 2.0, 2.0, 7.0, 3.0, -7.0, 4.0, -2.0, -6.0, -6.0, -3.0, -8.0, 10.0, 6.0, 6.0, 4.0, -9.0, -8.0, 1.0, 3.0, -2.0, 1.0, -10.0, 10.0, 9.0, 1.0, 7.0, -8.0, -6.0, -5.0, -7.0, -6.0, -10.0, -2.0, 9.0, 6.0], [7.0, 3.0, -6.0, -9.0, 5.0, -2.0, 7.0, 9.0, -2.0, -8.0, -6.0, 5.0, -6.0, -6.0, 4.0, -5.0, -10.0, -3.0, -7.0, -8.0, 5.0, 2.0, 10.0, -6.0, 3.0, -3.0, -7.0, -2.0, -2.0, -9.0, -2.0, 5.0, -9.0, -4.0, 8.0, 0.0, 0.0, -8.0, 0.0, -1.0, 2.0, 8.0, 10.0, 0.0, -9.0, -6.0, 4.0, 5.0, 9.0, 8.0], [-5.0, 4.0, 1.0, 5.0, -3.0, -9.0, 7.0, 1.0, 10.0, 6.0, 7.0, 10.0, 5.0, -5.0, 5.0, 3.0, 8.0, 5.0, -1.0, -9.0, 8.0, -6.0, 2.0, -6.0, 8.0, -6.0, -1.0, -6.0, -2.0, 2.0, 8.0, 6.0, -1.0, -9.0, -10.0, 1.0, -10.0, -10.0, 3.0, 6.0, 8.0, 2.0, 6.0, -3.0, -1.0, -5.0, 2.0, 6.0, 9.0, -8.0], [6.0, 4.0, -2.0, 4.0, -1.0, -2.0, -3.0, -8.0, 7.0, 9.0, 2.0, 0.0, 5.0, 9.0, 0.0, 4.0, -10.0, -10.0, 3.0, -7.0, 6.0, -8.0, 1.0, -1.0, -8.0, 4.0, -7.0, 0.0, 9.0, -8.0, 2.0, -1.0, -10.0, -8.0, 8.0, -3.0, 7.0, 10.0, 3.0, -2.0, -6.0, -5.0, 7.0, -8.0, -2.0, -7.0, -10.0, 3.0, -4.0, 4.0], [10.0, 1.0, 6.0, 8.0, -1.0, -1.0, -1.0, -8.0, 5.0, 5.0, 7.0, -1.0, 7.0, 8.0, 2.0, 1.0, -6.0, -10.0, 0.0, 0.0, 2.0, -2.0, 5.0, -9.0, 6.0, 7.0, 9.0, -9.0, 9.0, 0.0, 3.0, 1.0, -8.0, -9.0, 8.0, 6.0, 2.0, -7.0, 5.0, -9.0, 8.0, 4.0, 5.0, 5.0, -8.0, -7.0, -1.0, 6.0, 7.0, 3.0], [2.0, 7.0, -3.0, -7.0, 6.0, 5.0, 2.0, 8.0, 9.0, -10.0, -8.0, -6.0, -7.0, 9.0, -7.0, -5.0, 4.0, 8.0, -10.0, 1.0, -6.0, 9.0, -8.0, -7.0, 7.0, 5.0, 10.0, -5.0, 7.0, 9.0, -6.0, 3.0, -7.0, -9.0, -9.0, 6.0, 0.0, 3.0, 0.0, 10.0, -6.0, 4.0, -3.0, -10.0, -2.0, -2.0, 4.0, -6.0, -3.0, -6.0], [-2.0, -6.0, -4.0, 8.0, -1.0, -7.0, -9.0, 7.0, 10.0, 9.0, -10.0, -7.0, -8.0, 0.0, 0.0, 5.0, 1.0, 5.0, 8.0, 2.0, -2.0, 3.0, -10.0, 4.0, -8.0, 5.0, -1.0, -10.0, -7.0, 10.0, -8.0, -7.0, 7.0, -5.0, 9.0, -2.0, 6.0, 4.0, 0.0, 7.0, -4.0, -8.0, -9.0, -2.0, -9.0, -5.0, 6.0, -3.0, 10.0, 10.0], [10.0, 7.0, 1.0, 5.0, 0.0, -3.0, 1.0, -7.0, -10.0, 8.0, 2.0, -2.0, 1.0, -10.0, 6.0, 5.0, -7.0, -9.0, -2.0, -6.0, 2.0, -2.0, 8.0, 3.0, -2.0, 6.0, 9.0, -2.0, -7.0, -6.0, 5.0, -4.0, -10.0, 2.0, 9.0, -3.0, -9.0, 0.0, -10.0, 10.0, -1.0, 0.0, -2.0, -4.0, -8.0, 3.0, -7.0, 0.0, -6.0, -8.0], [7.0, -5.0, 1.0, -5.0, 4.0, -9.0, -8.0, -6.0, 8.0, -10.0, -9.0, -6.0, 6.0, 4.0, 8.0, -8.0, -2.0, -10.0, -3.0, 0.0, 10.0, -1.0, 4.0, 2.0, 2.0, 2.0, 2.0, -9.0, -10.0, 4.0, 1.0, 0.0, -10.0, 1.0, 10.0, -8.0, 10.0, 1.0, 9.0, -1.0, -4.0, 4.0, -8.0, -1.0, 4.0, 6.0, 2.0, -1.0, -5.0, 9.0], [2.0, 5.0, 4.0, 6.0, -8.0, 10.0, -7.0, 2.0, 5.0, 9.0, -2.0, 10.0, 1.0, 9.0, 10.0, 6.0, -9.0, -2.0, -8.0, 10.0, -7.0, -2.0, -1.0, -5.0, -4.0, 2.0, 6.0, -5.0, -1.0, 2.0, -10.0, -6.0, 2.0, -2.0, 4.0, -8.0, -9.0, 6.0, 2.0, -1.0, -1.0, -5.0, 7.0, 0.0, -2.0, -6.0, 2.0, 8.0, -6.0, -3.0], [0.0, 8.0, -2.0, -8.0, 10.0, -10.0, 2.0, -5.0, 5.0, 4.0, -6.0, -3.0, 7.0, -6.0, -9.0, -10.0, 10.0, 5.0, -8.0, -1.0, -2.0, -7.0, -2.0, -5.0, -2.0, 0.0, -9.0, 6.0, -10.0, -6.0, 0.0, 4.0, 4.0, -1.0, 9.0, -6.0, 4.0, 3.0, -5.0, 2.0, -3.0, 1.0, -6.0, -5.0, -10.0, -4.0, -7.0, -1.0, -10.0, 0.0], [10.0, 3.0, 3.0, 0.0, 4.0, -6.0, -3.0, 3.0, 2.0, -1.0, -8.0, -2.0, -6.0, -10.0, 2.0, -9.0, 10.0, -9.0, -9.0, 8.0, -9.0, -3.0, -6.0, -10.0, 0.0, -3.0, 10.0, 3.0, -2.0, -9.0, 7.0, -3.0, 3.0, 6.0, -9.0, 8.0, 5.0, 2.0, 3.0, 3.0, -1.0, 8.0, -10.0, -9.0, 0.0, 1.0, 10.0, 0.0, -6.0, -6.0], [2.0, 6.0, -9.0, -8.0, -5.0, 9.0, 2.0, 7.0, 0.0, 3.0, 8.0, 9.0, 0.0, 6.0, -9.0, 4.0, -4.0, 7.0, 8.0, -6.0, 2.0, -5.0, 3.0, -8.0, 1.0, 8.0, -4.0, 3.0, -10.0, 6.0, 0.0, -9.0, 6.0, -1.0, 0.0, 9.0, 1.0, 9.0, 8.0, -7.0, 6.0, -8.0, 7.0, -3.0, -2.0, 4.0, 9.0, 4.0, 1.0, -5.0], [9.0, -7.0, 0.0, 4.0, 0.0, -9.0, 4.0, 8.0, -9.0, -5.0, -10.0, -8.0, 6.0, -10.0, -8.0, 4.0, -10.0, 8.0, -2.0, -3.0, -3.0, 3.0, -6.0, -4.0, 5.0, -1.0, -6.0, -4.0, -1.0, -9.0, 6.0, 2.0, -9.0, -4.0, -9.0, -9.0, 2.0, 4.0, -10.0, -6.0, -3.0, -5.0, 1.0, -8.0, 6.0, 2.0, -7.0, 4.0, -3.0, 7.0], [3.0, 9.0, 7.0, 8.0, -1.0, 4.0, 10.0, -8.0, 0.0, -8.0, -2.0, -8.0, -8.0, -3.0, -7.0, -5.0, -9.0, -9.0, 7.0, -1.0, 9.0, -2.0, -7.0, -2.0, 6.0, -7.0, -9.0, -4.0, 5.0, -7.0, -6.0, -7.0, 5.0, 7.0, -3.0, 4.0, 0.0, -4.0, -9.0, 5.0, -7.0, 0.0, 2.0, -8.0, 1.0, -5.0, 0.0, -2.0, -4.0, 2.0], [8.0, -1.0, 5.0, -10.0, 6.0, 10.0, -8.0, -9.0, -7.0, 5.0, 3.0, 2.0, 1.0, 1.0, 1.0, 6.0, 0.0, 6.0, 9.0, 6.0, 6.0, -2.0, 2.0, -7.0, -6.0, 4.0, 9.0, -5.0, 1.0, 2.0, -8.0, 7.0, 2.0, 3.0, 9.0, 2.0, -7.0, -3.0, -2.0, -2.0, -2.0, -8.0, -5.0, -6.0, 4.0, 2.0, 7.0, 4.0, 1.0, -10.0], [0.0, 2.0, -9.0, -6.0, 5.0, 2.0, -10.0, 5.0, 7.0, 9.0, -10.0, -5.0, -1.0, -6.0, -9.0, 6.0, 5.0, 0.0, -5.0, -6.0, 0.0, -8.0, 4.0, -1.0, 6.0, 9.0, -3.0, -2.0, 4.0, -9.0, -7.0, -3.0, -7.0, 10.0, 9.0, -4.0, 2.0, -6.0, -3.0, 3.0, -6.0, -7.0, -8.0, -4.0, 2.0, 4.0, 4.0, 6.0, 6.0, 9.0], [8.0, 3.0, 9.0, -10.0, -1.0, 10.0, -1.0, -9.0, 4.0, 9.0, 9.0, -7.0, -4.0, 10.0, -4.0, 1.0, -3.0, -6.0, -5.0, -3.0, 8.0, -2.0, -9.0, -4.0, -6.0, -10.0, 3.0, -4.0, 3.0, 7.0, 5.0, 4.0, -5.0, -7.0, 5.0, -3.0, 5.0, 10.0, -5.0, -4.0, -6.0, 1.0, -2.0, -8.0, -1.0, 5.0, 6.0, -4.0, 2.0, -4.0], [-8.0, -1.0, 0.0, -3.0, 8.0, -4.0, -4.0, 0.0, 0.0, -4.0, -9.0, -9.0, 4.0, -7.0, 2.0, 10.0, 9.0, 10.0, -6.0, 2.0, 2.0, 9.0, 1.0, 8.0, 2.0, 7.0, -9.0, 2.0, 7.0, 1.0, -4.0, 7.0, 0.0, 5.0, 5.0, 4.0, -3.0, -4.0, 0.0, 10.0, 0.0, -9.0, 6.0, 1.0, 9.0, 9.0, 7.0, 1.0, -2.0, -6.0], [-5.0, -6.0, 3.0, -9.0, -7.0, 7.0, 8.0, 5.0, -4.0, -2.0, -5.0, 6.0, 3.0, 0.0, 0.0, -5.0, -8.0, -2.0, 6.0, 4.0, 8.0, -8.0, -7.0, 0.0, -5.0, -4.0, -1.0, -8.0, 1.0, 7.0, -1.0, 2.0, -10.0, 7.0, 9.0, 7.0, 9.0, -8.0, 2.0, 0.0, 9.0, -10.0, -1.0, -8.0, 7.0, -8.0, 4.0, -5.0, 4.0, 10.0], [10.0, 9.0, 5.0, 10.0, -4.0, -4.0, -2.0, 9.0, -5.0, 4.0, 10.0, -8.0, -9.0, -9.0, 7.0, -5.0, -5.0, 5.0, -9.0, 7.0, 2.0, 2.0, 8.0, 10.0, 2.0, 4.0, -1.0, -5.0, 1.0, -8.0, 0.0, -1.0, 8.0, 7.0, 8.0, -10.0, -6.0, 6.0, 9.0, 1.0, -10.0, -8.0, 10.0, -6.0, 0.0, 3.0, 9.0, -7.0, 0.0, -5.0], [-9.0, 0.0, 5.0, 4.0, -4.0, -1.0, 4.0, 2.0, 5.0, -2.0, 7.0, -4.0, -9.0, 2.0, -5.0, 3.0, -10.0, 7.0, -10.0, -1.0, -10.0, -7.0, 3.0, -10.0, 7.0, -6.0, -6.0, -4.0, 3.0, 3.0, -2.0, -6.0, 1.0, 7.0, -9.0, -6.0, -4.0, -10.0, 0.0, 3.0, -10.0, -1.0, 6.0, 4.0, -4.0, 2.0, 5.0, -5.0, 9.0, 1.0], [8.0, 4.0, -4.0, -5.0, 8.0, 1.0, 7.0, -7.0, 5.0, -7.0, 0.0, 10.0, 1.0, 1.0, -4.0, -10.0, 0.0, -2.0, -7.0, -2.0, 1.0, -2.0, -7.0, -6.0, -4.0, -8.0, 6.0, -3.0, 7.0, 4.0, 2.0, 2.0, -2.0, 5.0, 4.0, -3.0, 7.0, 7.0, -7.0, 6.0, -4.0, -3.0, -6.0, 3.0, 2.0, -2.0, 2.0, -9.0, -6.0, -2.0], [-7.0, 9.0, 10.0, -9.0, -3.0, -2.0, 3.0, -5.0, -6.0, 6.0, -7.0, -6.0, -5.0, -7.0, 3.0, -9.0, 5.0, -1.0, 6.0, 10.0, -3.0, -1.0, 10.0, 2.0, -2.0, -1.0, -8.0, 10.0, -10.0, -1.0, -10.0, 1.0, -2.0, -5.0, 7.0, 10.0, -2.0, 8.0, -5.0, 5.0, -5.0, 6.0, -9.0, 9.0, 5.0, -10.0, 9.0, 7.0, 6.0, -10.0]]) b4 = np.array( [234.0, 598.0, 95.0, 123.0, -839.0, 666.0, -235.0, -199.0, -514.0, 28.0, 600.0, 154.0, -122.0, -390.0, -244.0, -289.0, 145.0, 1114.0, 447.0, -151.0, -730.0, 12.0, -43.0, -123.0, -514.0, 112.0, 276.0, -527.0, 235.0, 51.0, 790.0, 14.0, 851.0, -44.0, 233.0, 39.0, -680.0, 793.0, 130.0, -1186.0, -989.0, 168.0, 350.0, -398.0, 182.0, -535.0, 797.0, -522.0, 2.0, -271.0]) ### Aufgabe 1 ################################################################## def forwardSubstitution(L,b): n = len(L) y = np.zeros(n) y[0] = b[0] / L[0][0] for i in range(1,n): # y_i = (b_i - sum_{j=1}^{i-1} l_{i,j} y_j) / l_{i,i} y[i] = b[i] for j in range(i): y[i] = y[i] - L[i][j]*y[j] y[i] = y[i] / L[i][i] return y def backwardSubstitution(R, y): n = len(R) x = np.zeros(n) x[n-1] = y[n-1]/R[n-1][n-1] for i in range(n-2, -1, -1): # x_i = (y_i - sum_{j=i+1}^n r_{i,j} x_j) / r_{i,i} x[i] = y[i] for j in range(i+1,n): x[i] = x[i] - R[i][j]*x[j] x[i] = x[i] / R[i][i] return x ### Aufgabe 2 ################################################################## def lrFactorization(AA): # ohne Pivotisierung A = AA.copy() n = len(A) L = np.zeros((n,n)) for j in range(n): L[j][j] = 1 for i in range(j+1,n): L[i][j] = A[i][j] / A[j][j] A[i][j] = 0 # 0 explizit eintragen nicht berechnen # von der i-ten Restzeile das l_{i,j}-fache der j-ten Zeile abziehen for k in range(j+1,n): A[i][k] = A[i][k] - L[i][j] * A[j][k] return L, A ### Aufgabe 3 ################################################################## def solveLES(A, b): L, R = lrFactorization(A) # A = L*R y = forwardSubstitution(L,b) # loese L*y = b x = backwardSubstitution(R, y) # loese R*x = y return x ### Aufgabe 4 ################################################################## def swapRows(M, j, i, fr, to): # Vertausche in der Matrix M die Zeilen i und j for k in range(fr, to): # aber nur zwischen den Spalten fr und to. tmp = M[j][k] M[j][k] = M[i][k] M[i][k] = tmp def searchPivot(A, j): # suche in der j-ten Spalte von A unterhalb n = len(A) # der Diagonal das betragsmaessig groesste absPivot = abs(A[j][j]) # Element ipivot = j for i in range(j+1,n): absaij = abs(A[i][j]) if absaij > absPivot: ipivot= i absPivot = absaij return ipivot def lrFactorizationWithPivot(AA): A = AA.copy() n = len(A) L = np.zeros((n,n)) pi = np.array(list(range(n))) # Permutation fuer die Zeilenvertauschungen for j in range(n): ipivot = searchPivot(A, j) if ipivot != j: # wenn Pivotelement nicht auf der Diagonalen # In A die Zeilen j und ipivot tauschen # ab Spalte j bis Spalte n (exklusive) swapRows(A, j, ipivot, j, n) # In L die Zeilen j und ipivot tauschen # ab Spalte 0 bis Spalte j (exklusive) swapRows(L, j, ipivot, 0, j) pi[ipivot], pi[j] = pi[j], pi[ipivot] # Tausch in pi merken L[j][j] = 1 for i in range(j+1,n): L[i][j] = A[i][j] / A[j][j] A[i][j] = 0 for k in range(j+1,n): A[i][k] = A[i][k] - L[i][j] * A[j][k] return L, A, pi def solveLESWithPivot(A, b): L, R, pi = lrFactorizationWithPivot(A) # P(pi) * A = L * R c = b[pi] # auf rechte Seite Zeilenvertauschungen anwenden y = forwardSubstitution(L,c) x = backwardSubstitution(R, y) return x ### Tests ###################################################################### x1 = solveLES(A1, b1) print(x1) x1 = solveLESWithPivot(A1, b1) print(x1) x2 = solveLES(A2, b2) print(x2) x2 = solveLESWithPivot(A2, b2) print(x2) x3 = solveLES(A3, b3) print(x3) x3 = solveLESWithPivot(A3, b3) print(x3) # LR-Zerlegung fuer vierte Matrix nur mit Pivotisierung machbar x4 = solveLESWithPivot(A4, b4) print(x4)