| 1. |
- Arévalo, Carmen, et al.
(author)
-
Convergence of multistep discretizations of DAEs
- 1995
-
In: BIT. - 0006-3835. ; 35:2, s. 143-168
-
Journal article (peer-reviewed)abstract
- Standard ODE methods such as linear multistep methods encounter difficulties when applied to differential-algebraic equations (DAEs) of index greater than 1. In particular, previous results for index 2 DAEs have practically ruled out the use of all explicit methods and of implicit multistep methods other than backward difference formulas (BDFs) because of stability considerations. In this paper we embed known results for semi-explicit index 1 and 2 DAEs in a more comprehensive theory based on compound multistep and one-leg discretizations. This explains and characterizes the necessary requirements that a method must fulfill in order to be applicable to semi-explicit DAEs. Thus we conclude that the most useful discretizations are those that avoid discretization of the constraint. A freer use of e.g. explicit methods for the non-stiff differential part of the DAE is then possible.
|
|
| 2. |
- Arévalo, Carmen, et al.
(author)
-
Improving the accuracy of BDF methods for index 3 dierential algebraic equations
- 1995
-
In: BIT. - 0006-3835 .- 1572-9125. ; 35:3, s. 297-308
-
Journal article (peer-reviewed)abstract
- Methods for solving index 3 DAEs based on BDFs suffer a loss of accuracy when there is a change of step size or a change of order of the method. A layer of nonuniform convergence is observed in these cases, and O(1) errors may appear in the algebraic variables. From the viewpoint of error control, it is beneficial to allow smooth changes of step size, and since most codes based on BDFs are of variable order, it is also of interest to avoid the inaccuracies caused by a change of order of the method. In the case of BDFs applied to index 3 DAEs in semi-explicit form, we present algorithms that correct to O(h) the inaccurate approximations to the algebraic variables when there are changes of step size in the backward Euler method. These algorithms can be included in an existing code at a very small cost. We have also described how to obtain formulas that correct the O(1) errors in the algebraic variables appearing after a change of order.
|
|
| 3. |
- Arévalo, Carmen, et al.
(author)
-
Stabilized multistep methods for index 2 Euler-Lagrange DAEs
- 1996
-
In: BIT. - 0006-3835. ; 36:1, s. 1-13
-
Journal article (peer-reviewed)abstract
- We consider multistep discretizations, stabilized by β-blocking, for Euler-Lagrange DAEs of index 2. Thus we may use “nonstiff” multistep methods with an appropriate stabilizing difference correction applied to the Lagrangian multiplier term. We show that order p =k + 1 can be achieved for the differential variables with order p =k for the Lagrangian multiplier fork-step difference corrected BDF methods as well as for low order k-step Adams-Moulton methods. This approach is related to the recently proposed “half-explicit” Runge-Kutta methods.
|
|
| 4. |
|
|
| 5. |
- Burdakov, Oleg, 1953-
(author)
-
A greedy algorithm for the optimal basis problem
- 1997
-
In: BIT Numerical Mathematics. - : Springer. - 0006-3835 .- 1572-9125. ; 37:3, s. 591-599
-
Journal article (peer-reviewed)abstract
- The following problem is considered. Given m+1 points {x i }0 m in R n which generate an m-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the form x i −x j . This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrix f′ of a nonlinear mappingf by using values off computed at m+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination of m pairs {x i ,x j }. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm in O(m 2) time. The complexity of this reduction is equivalent to one m×n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is below O(n 2.376) for m=n. Applications of the algorithm to interpolation methods are discussed.
|
|
| 6. |
- Crouzeix, Michel, et al.
(author)
-
The stability of rational approximations of analytic semigroups
- 1993
-
In: BIT Numer. Math.. - 0006-3835 .- 1572-9125. ; 33:1, s. 74-84
-
Journal article (peer-reviewed)abstract
- This paper contains two new characterizations of generators of analytic semigroups of linear operators in a Banach space. These characterizations do not require use of complex numbers. One is used to give a new proof that strongly elliptic second order partial differential operators generate analytic semigroups inL p , 1
|
|
| 7. |
- Edlund, Ove
(author)
-
Linear M-estimation with bounded variables
- 1997
-
In: BIT Numerical Mathematics. - 0006-3835 .- 1572-9125. ; 37:1, s. 13-23
-
Journal article (peer-reviewed)abstract
- A subproblem in the trust region algorithm for non-linear M-estimation by Ekblom and Madsen is to find the restricted step. It is found by calculating the M-estimator of the linearized model, subject to anL 2-norm bound on the variables. In this paper it is shown that this subproblem can be solved by applying Hebden-iterations to the minimizer of the Lagrangian function. The new method is compared with an Augmented Lagrange implementation.
|
|
| 8. |
- Gulliksson, Mårten
(author)
-
Iterative refinement for constrained and weighted linear least squares
- 1994
-
In: Bit: numerical mathematics. - 0006-3835. ; 34:2, s. 239-253
-
Journal article (peer-reviewed)abstract
- We present an algorithm for mixed precision iterative refinement on the constrained and weighted linear least squares problem, the CWLSQ problem. The approximate solution is obtained by solving the CWLSQ problem with the weightedQR factorization [6]. With backward errors for the weightedQR decomposition together with perturbation bounds for the CWLSQ problem we analyze the convergence behaviour of the iterative refinement procedure. In the unweighted case the initial convergence rate of the error of the iteratively refined solution is determined essentially by the condition number. For the CWLSQ problem the initial convergence behaviour is more complicated. The analysis shows that the initial convergence is dependent both on the condition of the problem related to the solution,x, and the vector lambda=Wr, whereW is the weight matrix andr is the residual. We test our algorithm on two examples where the solution is known and the condition number of the problem can be varied. The computational test confirms the theoretical results and verifies that mixed precision iterative refinement, using the system matrix and the weightedQR decomposition, is an effective way of improving an approximate solution to the CWLSQ problem.
|
|
| 9. |
- Gulliksson, Mårten
(author)
-
On the modified Gram-Schmidt algorithm for weighted and constrained linear least squares problems.
- 1995
-
In: Bit: numerical mathematics. - 0006-3835. ; 35:4, s. 453-468
-
Journal article (peer-reviewed)abstract
- A framework and an algorithm for using modified Gram-Schmidt for constrained and weighted linear least squares problems is presented. It is shown that a direct implementation of a weighted modified Gram-Schmidt algorithm is unstable for heavily weighted problems. It is shown that, in most cases it is possible to get a stable algorithm by a simple modification free from any extra computational costs. In particular, it is not necessary to perform reorthogonalization. Solving the weighted and constrained linear least squares problem with the presented weighted modified Gram-Schmidt algorithm is seen to be numerically equivalent to an algorithm based on a weighted Householder-likeQR factorization applied to a slightly larger problem. This equivalence is used to explain the instability of the weighted modified Gram-Schmidt algorithm. If orthogonality, with respect to a weighted inner product, of the columns inQ is important then reorthogonalization can be used. One way of performing such reorthogonalization is described. Computational tests are given to show the main features of the algorithm.
|
|
| 10. |
|
|
