Does an implicit Runge Kutta scheme applied on a nonlinear ODE give a nonlinear set of equations to solve in each step?

Question

We want to approximately solve an ODE $$\frac{dy}{dt} = f(y,t)$$ with the Runge Kutta method $$y_{n+1} = y_n + h \sum_{i=1}^s b_i k_i$$ $$k_i = f\left(y_n + h \sum_{j=1}^s a_{ij} k_j,\,t_n + c_i h\right)$$

For explicit methods the matrix $a$ is strictly lower triangular and thus you can determine $k_i$ explicitly without solving any set of equations. For implicit methods on the other hand, $a$ is not lower triangular and calculating $k_i$ becomes more complicated since you have to solve a set of equations.

I was of the impression that for implicit RK methods you would have to solve a linear set of equations, but looking at the definition of $k_i$ it looks to me as if $f(y,t)$ is nonlinear the system of equations determining $k_i$ will also be nonlinear. Is this correct?

If so, does this render implicit RK methods quite useless for nonlinear $f(y,t)$s because of the heavy computational power required to solve the nonlinear equationset?

For more background on RK methods take a look at: List of RK methods, RK methods in general.

Answer 1

This is the problem with implicit schemes (any kind of schemes) applied for the solution of nonlinear equations. You do need to solve a nonlinear equation (or even worse, a nonlinear system) at each step, and usually this done with Newton's method. There are also hybrid methods, implicit-explicit, where the implicit corresponds to the linear part and the explicit to the nonlinear one. (See for exmple the works of Ascher, Ruuth et al.)

Answer 2

This is not a research-level question; the answers can be found in any undergraduate text on the subject.

it looks to me as if f(y,t) is nonlinear the system of equations determining ki will also be nonlinear. Is this correct?

Yes.

If so, does this render implicit RK methods quite useless for nonlinear f(y,t)s because of the heavy computational power required to solve the nonlinear equationset?

No.